[wewyor]

Linode, if you don't need the cloud way of doing things (it is much harder to create your own image and use it on multiple servers, though doable it isn't the recommended way).

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.

[pilib]

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.