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).
Elegance and truth are inversely related. -- Becker's Razor