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).
The means-and-ends moralists, or non-doers, always end up on their ends without any means. -- Saul Alinsky