I used powweb for my site,
http://www.the-kd.com They are rarely ever down, and if they are it's for a matter of minutes while they upgrade their servers (which they've done a couple times this year, providing customers with more bandwidth and space, for free). Their prices can't be beat, and neither can their support. I'd suggest you chose Powweb for your host.