My vote is for ARP Networks. http://www.arpnetworks.com/ http://www.arpnetworks.com/ They officially support FreeBSD and OpenBSD as well as various Linux dist

My vote is for ARP Networks. http://www.arpnetworks.com/ http://www.arpnetworks.com/ They officially support FreeBSD and OpenBSD as well as various Linux distributions, and since their VPSs are KVM rather than Xen-based you don't have to worry about building or running a Xen kernel inside your VM. In my experience they're very reliable.