This response assumes that you're hosting something that's important to you. There is always a certain "you get what you pay for" aspect to hosting. If you pay for your hosting and have an actual agreement, then the provider is more likely to provide support and be generally accountable.
I've had some experience with probably 30-40 hosts over the last ten years in web development. Out of the small number that seemed to be worth the money, there were even fewer who could provide the whole package -- up-to-date software, stability, accessibility, configurability, accountability, etc. -- for less than $10/mo.
Downtime is unavoidable, so I don't consider it a fault of a hosting company. It just happens. What matters is how quick and transparent the recovery process is.
Dreamhost is one place to look. I have heard one complaint about them, concerning downtime, but years of good feedback.
HostExcellence has been reliable for one of my clients for several years, with the exception of some downtime on one of their database servers.
I use
TextDrive for certain kinds of sites now, as their installed software packages and developer-centric approach are great for some projects. But their general focus is on web developers, not more casual users.
GoDaddy just called me the other day and tried to convince me to give their hosting a shot. I agree about their customer service.