I can't make any direct recommendations. Since you asked about OpenBSD, and this is in an OpenBSD subforum, here's a link to a recent discussion about providers who offer OpenBSD hosting, from the misc@ mailing list:
The thread starts here: ==>
http://marc.info/?l=openbsd-misc&m=123533998914160&w=2
Note: OpenBSD is not a requirement for any of these VPN or encrypted-proxy technologies.