Try rackspacecloud servers (http://www.rackspacecloud.com) - uses pretty much the same backend as slicehost (slicehost owned by rackspace). I find them cheaper as it's not a fixed cost, but pay as you go.
I run everything on Rackspace Cloud Servers, from SaaS apps to a very large Ecommerce site, and I'm extremely happy with them.