Thought I'd chime in:
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.
