I use
www.One2Host.com . Back when I first got them, they sucked. Lots of downtime. This was when their servers were based in the UK. Right at a year ago, they migrated their servers to the US, and since, my site has been down maybe one or two times and for no longer than a couple hours.
A buddy of mine uses
www.DreamHost.com and seems to be happy with it.