I use both Amazon (past 6 months) and openHosting (past 3 years). OpenHosting has been nice, with the occasional service disruption but really good technical support by people in the know. I am using their old infrastructure (vServer) but they have a new version out that looks cool (KVM). http://www.openhosting.com/cloud-hosting-features/hosting-demo/
What is your preference?
Currently Australia only, although if you are in the US and find it interesting, email me.
Things like stackscripts and on demand servers make it closer to the cloud style but not really. They are a good VPS provider with good support and reliability.
They have an API for which you have documentation, stackscripts and other goodies, try it out.
You can go with slicehost as well, although I haven't tried them.
I have never tried them, but they seem pricey, and I get the feeling that when you try to get technical support in this very big providers you deal with some intern or temporary worker who has been there for 6 months, not the people who set up the datacenter from the ground up.
Also small companies know their only chance is to never loose a customer.