upvote for linode, I'm using them for my personal server for over a year and I'm very satisfied.
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.
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.