Just wanted to give a quick plug for JohnCompanies. They offer "virtual private server" hosting (full instance of FreeBSD, Debian, or RedHat running in user-mode-linux type configuration) with nice discounts for open source developers. I've been using them for a while (hosting this blog on an instance of RedHat, actually) and have been more than pleased with them.
Sorry to advertise on my blog, but wanted to give them some good chatter =) I am a (very happy) customer of theirs, but am not a shareholder, nor do I profit directly from them (just from the envelopes full of money random strangers keep sending me for doing open source work ;-).