I've only used Rackspace so far, so just providing my feedback for that.
Rackspace is cheap, as far as on demand goes. It's very easy to load up a server, configure it how you want, then save off an image to restore later. At high traffic times, the creation and save seems to take a bit longer.
Latency seems to be a little on the high side. Simple comet js pushes take a bit longer than they should, and outgoing queries are also similarly slow (i.e. sending out a request to someone else's API). Inbound standard traffic seems speedy enough.