VPS — это виртуальный приватный сервер. Для вашего удобства и экономии целый физический сервер программно делится на несколько виртуальных серверов со своими ресурсами (CPU, ОЗУ, Диск).
Этот сервер постоянно подключен к Сети и работает без перебоев. Он полностью изолирован от соседей по физическому серверу. За счет такого решения стоимость сервера может быть совсем небольшой - от 45 рублей/мес.
VPN (например, OpenVPN) можно развернуть на такой VPS/VDS за пару шагов. Лично я ставил по инструкции, проблем не возникло.
Это виртуальный сервер (VPS/VDS) на котором разворачивается VPN. Как правило хостинг-компании не выделяют специальные тарифы для организации VPN. Практически на любом VPS/VDS можно его реализовать.