It seems like only smaller VPS services offer first-class support for BSD. There's a few out there besides RootBSD. ARP Networks [0] is one; it's got pretty reasonable rates.
[1] Fall of 2001.
[2] Yes, Verio had those weird virtuals running on e10ks, but JC was the first to offer the VPS as we all came to know it.