http://orionvm.com.au is cool, easy to use and stupidly fast. (Disks 60% faster then a raid 10 of 15K SAS disks, #1 in a whole suite of benchmarks http://orionvm.com.au/blog/3rd-Party-Performance-Benchmarks/)

Currently Australia only, although if you are in the US and find it interesting, email me.

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.

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.

http://www.softlayer.com/ seems to be a good provider. Haven't used them as yet but will be making the switch from Amazon as soon as all of my instances are up.

I'm a rackspace guy.

What is it that you like about rackspace?

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.

Rackspace support leaves much to be desired but it's 100x better than even Premium EC2 support (in my experience).