Adding to the posts in this list:
Shared host: Dreamhost. Been with them for nearly 5 years, never had a big problem. Occasionally had to harp on them for slow MySQL servers, but it's a shared host - comes with the territory.
VPS: Canadian Web Hosting (
http://www.canadianwebhosting.com/) or Steadfast (
http://steadfast.net/). Both have been great experiences for me on a few different projects.
Cloud host (for the uber-nerd): Rackspace - super cheap but you need to be able to setup your own server. Pain the ass overall though - only recommend if you actually need this level of hosting.
Amazon Cloud is OK... but it's ridiculously expensive.
My Hosting ##### list:
GoDaddy - it's GoDaddy
MediaTemple - shared hosting was slow, non-existent support
1&1 - their shared host is poorly setup and slow (apparently they do better with Microsoft hosting)
Primus - no support, uses Zeus web-server which isn't clear at the outset. Makes setting up anything open source a bloody pain in the ass.
Telus - not sure they actually understand what the internet is