Выбор VPN решения (VPS)?
Какую технологию туннеля/аутентификации выбрать?
НЕ pptp

Какой софт использовать для VPN сервера? Желательно:
- не дырявый из коробки
- с настройкой через вебинтерфейс
- на Дебиане (не обязательно)
softether, вебморды нет, но есть софт с гуём для удалённого администрирования; на счёт дырявости - проприетарщина всегда чёрный ящик, но это, насколько мне известно, единственное решение под никсы с гуём. Если без гуя - таки openvpn, но он без собственного клиента не работает, в отличие он нескольких вариантов, поддерживаемых softether (sstp, ipsec/l2tp, ipsec/ike)
С веб мордой вряд ли что-то найдете. Разве что на VPS воткнете что-то типа pfsence или аналогов.
Я голосую за openvpn :-)