Right now, I have Hetzner on my list, because I like unmetered to avoid overage charges. (it sucks that they dont offer CentOS)
I recently installed CentOS 4.4 remotely on a new server at Hetzner (via their LARA console) - it cost €25 for one-off LARA access, but that also let me easily partition and set up a software RAID-1 array, so I think it was worth it. They asked me to provide them with a CD ISO, which they burned for me and had booted from when I received my LARA access email. (I used one of the "Server CD" releases, since it fits on one CD and has all the basics.)
Their email support seemed to be slow-to-nonexistent over the run up to Christmas, and so far I've got nothing out of them on weekends - I haven't tried phoning, since nothing's been urgent enough to warrant the international call cost - but for the price I'm certainly not going to argue just yet.