Another vote for Linode. Not only do these guys know what they're doing, the support is top notch. They're very open about when problems pop up and inform us users and the world via several different forms (forum, irc, twitter).
"Even if you're on the right track, you'll get run over if you just sit there." -- Will Rogers