If more virtualized hosting providers offered BSDs (FreeBSD in particular) I would choose them over Ubuntu for servers.
I don't see it in their 'distro manager' thing
You can try it out locally by setting up Linux and running FreeBSD in domU. Then just transfer that image to Linode.
freeBSD 8 requires at least xen 3.3 to run in paravirt mode; this is why it won't work on ec2, so I don't know if that counts as a 'normal xen setup' -
The thing is, last I read FreeBSD8 was not stable under paravirt xen, and I was hoping to hear this had changed. Also, last I remember, it didn't work at all with more than one vcpu.
In that case I might as well give a shout-out to my current VPS host, ARP Networks:
http://www.arpnetworks.com/vps
They virtualize using KVM rather than Xen, so you can run any variety of OpenBSD, FreeBSD, NetBSD, or Linux without worrying about Xen support in your guest OS. Their performance seems as good as any other VPS host I've used (Xen or otherwise), I think the price is pretty good, and I haven't had any downtime to speak of so far. So I recommend giving them a try if you're looking.