http://www.rootbsd.net/ is another choice. I'm happy with them.

Linode has actually been able to do NetBSD for a while: http://www.linode.com/wiki/index.php/NetBSD_howto

With a little work I'm sure this version of FreeBSD can be installed on Linode as well.

FreeBSD is kind of another beast at this point in time, NetBSD support for xen is actually okay and it is pretty trivial to get it working, freebsd not so much.

Hopefully cperciva's work will pay off soon for a stable freebsd on Xen as I know there are plenty of users, me included, that would love this option.

Edit: and that linode post on how to get it running looks a bit dated