I couldn't test http://nqhost.com/ I wrote to this guys and telling them that I wanted to host sign.io inside a jail, but they were scared knowing that ssh was going to be open and didn't want me to host with them.
There are many other providers, but unfortunately are more interested on making quick money overselling the services that really providing a good solution.
Yahoo webhosting with shared hosting ftp+php+perl+mysql only but no root or shell access - http://business.yahoo.com/webhosting/details (they don't say FreeBSD but I've talked with their support and they confirmed it FreeBSD 4.x UNIX)
ARP Networks are pretty good - server is solid in terms of crashing, but their network drops every so often (I have nagios on it that frequently complains about five hosts in five DCs simultaneously, so I'm guessing it's their network) and while the support can be less-than-instant I've never been tearing my hair out waiting for them. Oh, they have native IPv6 too, if that's your thing.
I'm also running FreeBSD 8.2 on a Linode, and it's been fantastic. No v6, but it's been pretty solid under low-load. I'm about to fire up another one and flog it, to see if it barfs chunks or not... cperciva@ (and I'm guessing some others?) has done a ton of work on Xen-PV stuff for AWS, which Linode has benefited from significantly.
Both start at $20/mo for pretty reasonable quotas.
Oh, since I mentioned it, AWS' free tier isn't too bad, depending on what you want to do with it. The I/O quota is pretty low (I hit it enough to get charged 1~3c each month, which they then cancel because I'm guessing I'd be costing them money to collect it at that point), and IIRC there's been periods where performance is less than stellar but it can work out pretty cheap depending on what you actually want from it.