My vote is for ARP Networks.
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.