С чего начать VDS/VPS?
Сам был недавно в таком же выборе. Поэтому оставлю свою историю тут:
Полгода назад, я пробовал Digital Ocean, там с помощью купонов и подарков, можно получить 25-50 баксов на счету особо не заморачиваясь.   Устанавливал Vesta панель, вроде получилось, но за отсутствием времени оставил идею на потом. Из сложностей я бы отметил права на работу с файлами, dns, ssh.
Осмелев, месяц назад, я купил хостинг vps  у своего хостинг провайдера. В этот раз все стало в разы проще. 
По поводу установки самого важного окружения, могу посоветовать Vesta panel:
сама установка панели, со всем необходимым окружением ставится из двух команд на сервере. Причем после установки - у вас уже есть все необходимое, включая последний php. 
А далее, настраиваете, исходя из нужд, отдельно mysql, php и тд. 
Как вариант, для теста, попробуйте воспользоваться виртуальной машиной на компьютере своем.
С чего начать VDS/VPS?
С понимания того, что вас будут разводить на бабки непрерывно и постоянно. То "кнопка сама нажалась", то "патчкорд сам отлетел", то "винт сам умер" итд итп. Каждое обращение для пофиксить подобную проблему встанет вам в годовое обслуживание обычного шареда.