These are my recommended hosting providers of 2014, all of whom offer Linux machines running Ubuntu or Debian:
Linode offer a wide range of VPS solutions in multiple locations. They have a good community behind them with some great tutorials. Their control panel makes things easy to manage too. There are pay-more additions like load balancers so if you think you’re going to grow your sites quickly or get lots of traffic it’s worth going with them as a more mature hosting provider.

Digital Ocean have been making a big name for themselves in the past year. Their machines are much faster than a traditional VPS as they’re an SSD only hosting provider, so no old spinning disks to slow things down. They have a wide range of tutorials and Q&A sections on their site which are growing rapidly. The web interface is easy to use, but I’m not too keen on the spin-up process yet as they insist on providing you a password via email.

Bytemark offer a cloud platform similar to both Linode and Digital Ocean. They’re a smaller team based in the UK and the platform is still maturing, but Bytemark are always my first port of call for hosting services. They sponsor many open source events and projects, and even offer hosting to the Debian project.