Edited Sep 16, 2014:
Overall there is no perfect host in my opinion. You'll probably run into one issue or another at some point. A host that is good now may be not so good in a year. I have deleted my recommendations. I suggest that you search webhostingtalk.com for reviews. For VPS there is also lowendbox.com
Popular names are
Shared Hosting: hostgator.com
VPS: wiredtree.com, liquidweb.com, knownhost.com, futurehosting.com, servint.com
Dedicated: webnx.com, hetzner.de
As of Sep 2014 I am loking into thes SSD hosts: ramnode.com & linode.com
Our current setup (Sep 2014) contains
- SSD drives
- Debian
- Nginx