I've been a happy customer of ARP Networks [0] for about five years now (running Linux, FreeBSD, and OpenBSD hosts). I've pretty much moved everything off to my own servers (since I work for an ISP and can put whatever I want in our datacenters) but I do still have one VPS hosting a few websites.

Native IPv6 is enabled on every host which, as a network engineer, is a huge plus for me. Physical location is at One Wilshire in Los Angeles and ARP has great connectivity and lots of peering.

It's a small operation which, depending on your point of view, can be either a good thing or a bad thing. There is no "instant provisioning" (or wasn't, the last time I ordered a new host) so it may take a day or so for your host to be available for your use. On the other hand, you can often catch the owner in #arpnetworks on freenode and chat directly with him (or get quick answers to (general) questions from other happy customers). He's also on HN occasionally, if memory serves.

[0]: https://arpnetworks.com/

TransIP in the Netherlands offers OpenBSD VPSs https://www.transip.eu/vps/operating-systems/

I'm using filemedia[0]'s KVM-based offering. It supports custom ISOs (you can open a ticket to get a new ISO uploaded), so installing OpenBSD (5.4 at the time) was quite easy. You just have to make sure to use DHCP and not a static IP in the network configuration, otherwise the network stops working a few months later when the DHCP lease expires.

They also have a new Xen (PV or HVM) oferring, but I don't know how well OpenBSD would work with that.

Another possibility is iwStack[1], another KVM-based hosting provider.

[0] https://www.filemedia.de/ [1] http://iwstack.com/

RootBSD (https://www.rootbsd.net/services/virtual-servers-vps/) has OpenBSD VPS's (I'm guessing it'll be a little bit before they have 5.6 available).

You can install it yourself actually, even if they don't offer it right away.