Last August, after years of moderate dissatisfaction with my domain registration and site hosting arrangements, I signed up with Dreamhost.
I've been quite satisfied with them as a hosting service and even happier with their registrar services; you can see this from posts over the past six months. I was disappointed with their weak implementation of webdav services, but that's been a minor problem. Of course you need some geek genes to work with them, but less so than most alternatives.
If you want to keep things simple, DreamHost is a better Google Apps partner than Google -- especially now that Google is trying to hide the free stuff.
Dreamhost offers members kickbacks to facilitate recruitment. So you need to take my recommendation with more saline than usual, but if you independently decide to sign up you can use my promo code of KATEVA (our dog) and get $50 off your 1st year fee (and I get a kickback if you pay up). Be sure to check out other promo code deals however, the one on their home page looks remarkably good.
Dreamhost now offers "unlimited bandwidth" and "disk space" to new customers with the caveat that you can't be running a site designed to suck bandwidth. Existing customers can also upgade, It turns out I was somehow using more storage than I thought and was paying some modest overage fee, so I just did the free upgrade to "unlimited".
Lastly, unrelated to hosting, Dreamhost is offering an "apps" service (install Wordpress, etc) that's supposed to be free "forever" to beta testers (more invitation codes).