I just ordered a cloud server instance.
Lots of images available. They've got Fedora, CentOS, redHat, debian... and others I've never heard of
I think I'll choose Fedora 14 (Laughlin).
I've got a different server running Fedora and I like that it comes with YUM and all the repo's I need for all the little fancy modules I'm running