I've heard good things about both Linode (http://www.linode.com/) and
Slicehost (http://www.slicehost.com/), and briefly used a friend's
Linode account for some Supybot instances without issues.

-- 
Tony Yarusso
http://tonyyarusso.com/