Чем больше процессора, тем быстрее будет летать зашифрованный трафик.
Например, для 50 mbps зашифрованного openvpn трафика нужно одно ядро AMD туриона.
Чем больше памяти, тем больше всякого софта вы сможете запустить. Вообще по памяти оно всё не сильно прожорливое (100-200 mb RSS на инстанс), но всё же.
Смотреть нужно на канал до вас (ну или того, кто пользоваться будет). Т.е., если вы в России, то VDS должна быть явно не в США/Японии/Сингапуре.
Технология виртуализации - обязательно KVM, иначе будете мучаться с модулями ядра и просить у саппорта их включить. Можно Xen, но там может статься, что некоторые модули придется руками собирать.