My personal experience within the last 7 years:
* Softlayer – the best option in terms of quality of service, quality of hardware, quality and size of the infrastructure (geo distribution, etc).
* Rackspace – nice, until you grow enough to get relatively locked in and then your prices start to go up, provisioning time suffers and their service turns into shit.
* Steadfast – provisioning times up to a week, basically a joke in today's world.
* Some German/EU providers like Hetzner – dirt cheap option with desktop-like hardware, failing quickly. Service is nowhere near SL level.
I could go on and on about those, but other options were even more painful.
I've been running three 32GB servers (each with 3TB storage) with them for 2+ years now and the only outage I've experienced is the switch (5 port GBit) dying once. Hetzner tech replaced it in under an hour.
These three servers cost me €263/month (that's total, not each). Included in that monthly price is an additional IPv4 for each server, a private 5port Gbit switch, remote console access and 300GB of DC backup space.
There are probably better deals available now (i.e. more RAM at the same price) than the one I'm on since it's old and not offered on their site any more (/makes note to self to call Hetzner sales)
Hetzner and OVH both use cheap hardware, but IME it's not hard to use the same primitives you'd otherwise use in something like AWS to build in redundancy at a price point well below AWS.
I wouldn't want to do it, which is why I'd rather work for somebody who'd pay for AWS, but I think there's a thing in there somewhere for those who want to dig.
I could go on and on about those, but other options were even more painful.