Bare metal, the best is OVH. You get a server in 1h in France or in Canada. You can also get instances for pretty cheap but I have only used them as throw away test instances. Oh, they have free bandwidth between all their datacenters, even between Canada and France as they managed their own transatlantic links.
They have a very decent "private cloud" offer. The feedback is good but I am a bare metal + Ganeti[1] to manage my VMs kind of person.
If you like pure instances, I have also instance running on Gandi[2] infrastructure. My blog made several times the front page of HN and without special caching it handled extremely well the load (in fact, you could barely see the increase in CPU usage in the monitoring graph while seeing a huge increase of the outbound bandwidth).
Another good provider is Hetzner[3]. You need to pay attention to the server you select (ECC memory or not) but then they are reliable (I had a server with them for 4 years or so without a single issue).
In Europe, AWS is in Irland, I suppose it was for tax purpose that they selected this location, but from a latency point of view, this is stupid if you want to deliver packets in the South or East of Europe (and even part of Scandinavia because most of the time your route does IE, NL or FR, and then goes North).
Sorry for the long post... but at the end of the day, do your calculations. AWS is great if like Netflix you scale from 20% to 100% during the day[4] (the hit on the cache gives you how they scale) but if you are a normal shop without day/night activity because you are at global level or so well optimized that you just not need to scale (a single dedicated server with SSD is incredibly powerful nowadays) you simply do not need "the cloud". Just test with 1kâĴ, do a bit of maths, then select the best choice.
We also like & use most of those providers with our own food (http://comodit.com) to deploy/manage them, even if they are bare metal. We also mix them in hybrid cloud scenarios.
If you are okay with working on bare metal (i.e. no virtualization out of the box) than Hetzner (www.hetzner.de) is a very interesting partner. My experience with them is very good. Ex-colleagues are also happy with them.
