If you wish a full datacenter in the cloud (where you can have complete OS installed) you should go here:

http://daas.com/display/wwwdaas/Home

Jochen

Amazon EC2 will definitely be better than other because you get complete control over it.
I have configured a EC2 instance for the company I work. Its like configuring your own system.
You have to just create an instance then ssh into it. Then do whatever you want with it.

EC2 has the tools that make using and managing a cloud infrastructure. Rightscale and even tools like s3fox and elasticfox make ec2 dead easy.

Rightscale also now works with Eucalyptus, which is available with Ubuntu 9.04, so you can use some of those tools for private cloud deployments as well.

take a look at linode, they work well and include free dns, with retty good pricing