That's hard to say. It seems like many of them are good for a while, then their quality slips.
For example, I've been with Hostgator since September of 2009. I switched to them from Netfirms, based on recommendations right here in these forums. And I was very happy with the quality of the service until this year. In the past few months, my sites have been down or slow on way too many occasions.
I did some Googling, and found out that EIG (a huge Web hosting congomerate) has been buying up a number of Web hosting companies. EIG recently bought Hostgator, and now many people have been having service interruptions, myself included. Ironically, EIG bought out Netfirms a couple of years ago, and now also owns Bluehost.
So - I'm thinking of going with Dreamhost. I know they've had their downtime issues, but could they be any worse than Hostgator is now? Plus, you can sign up for a year's worth of hosting for just $2.95 a month: http://www.dreamhost.com/promo/hosting295/. A lot of pro Webmasters seem to like Dreamhost, which -as of yet - hasn't been swallowed up by EIG.
Anyone care to chime in? Dreamhost users? My account with Hostgator is up for renewal next month, so I too am interested in finding a good alternative.