Value: - Digital Ocean https://www.digitalocean.com/ (US-East, Amsterdam) [KVM/QEMU based, spinup time is under a minute, decent 'basic' API]
As a current customer of both companies, we use Digital Ocean to host our company VPN and development nodes, and PhoenixNAP to host our production sites. (Bandwidth at PhoenixNAP is billed @.05- per gb, very competitive compared to EC2 especially considering they use exclusively premium bandwidth)
Amazon, heroku etc aren't fast enough for us due to spin-up time. Basically when we get a particular command from a user, we need to do a LOT computation on many parallel machines, but for a short burst of time.
Keeping a whole cluster of machines reserved would be prohibitively expensive at this stage. We would prefer to keep a small base-load capacity reserved, and then spin up a large number of instance for a short time. Response time is key here.
It would be best if they were already up and running, waiting for a command, but idle most of the time. Fine if it's shared with others. Kind of like a computation insurance for short bursts of high-demand.
Anyone know any services like that?
In the US Hivelocity have great prices - http://hivelocity.net/
In Europe there's also Hetzner - http://www.hetzner.de/en/
Perhaps two options you might consider: buy (don't rent) your own hardware and get some colo space nearby. It can work out significantly cheaper and neither the hardware or rackspace has to be expensive.
The second option to minimize costs would be to rewrite the key parts of your algorithms in something like C, if you haven't already. If you're doing the heavy lifting in something like Ruby, or even Java, you're going to be wasting a lot of resources in a situation where it sounds like every cycle counts.
Hope this helps.
We are using DO ( value for money ) for a new service and A full nginx based site can be setup in under 60 - 80 seconds after cloning a basic image. New instances take a little less time.