Ask HN: Cloud hosting that doesn't suck?

I'm working for a small startup which is experiencing some growing pains with regard to application hosting. We have been using Amazon EC2 for a while to host our systems. We use them for everything -- production servers, staging servers, monitoring systems, backups. We're not happy and have never been. The main issue with Amazon is flaky performance, especially with regard to IO. Our Rails apps run at a crawl. Even their best configs have pretty slow per-core performance. We could buy a bunch of physical servers and colocate them for a fraction of the price Amazon costs us per year, and enjoy a tenfold performance increase. The second issue is the pricing structure, which does not allow for fine-grained resource allocation; the configurations Amazon offer are rarely ever "just right", and it's not possible to tweak them to save money when we can make do with something small and simple. Scaling horizontally to work around the resource granularity issue is not really an option as it would be too costly. There are some other technical issues that are tiresome to deal with, such as Amazon's dependency on a weird NAT structure that require ugly workarounds in our management systems (eg., Puppet). We have migrated a few hosts off Amazon over to Cloud Sigma, which we immediately perceived as having better CPU performance, and a _much_ nicer pricing structure where you essentially pay by by the gigahertz (CPU) and megabyte (RAM) in 5-minute intervals. However, we quickly met a wall with regard to IO, which is even worse than Amazon despite the fact that they use Linux KVM with local disks. I would like to hear about other people's experiences with other cloud hosting services. We need something that "just works" and provides performance comparable to non-virtual hosting. Colocated hosting is fine, too -- probably better, in fact -- as long as adding or removing hosts can be done quickly and painlessly through a web app. At this point we are even considering admitting defeat and just colocating everything. Any help would be appreciated. Note that we are in Europe, so any recommendations will need to take our location into consideration. Thanks!