Linode is pretty solid. They have had about 2(?) outages in the past year or so that I can remember. I've been using Linode since 2008 and am happy.
The linode library is pretty helpful too, especially if you are fairly new to linux or systems administration.