Anyone who has worked with me in the past couple of years will know that I have a very strong preference for recommending Amazon AWS as your IaaS provider of choice. It is mature, robust, performant, and has a whole raft of PaaS type features to make things easy and lower the sysadmin burden/requirement.
It also represents really good value for money to my mind, and what better way to learn about it from the free usage tier (if you stay within the fairly generous limits it truly is free). Since the introduction of the t2.micro node, and general purpose SSD storage (replacing t1.micro, which was rather memory cramped, and our old friendly spinning rust) it is a serious piece of virtual hardware for a rather special price.
There is, however, no such thing as a one-size fits all answer. Perhaps you need a UK IP address. Perhaps you want a better pricing plan on TB of data in and out from your VPS. Perhaps you don’t need all the fancy infrastructure capabilities, but just want a few Linux boxen “in the cloud”. If so, you could do a lot worse than to look at linode.com. I first had a shell on a linode many many many years ago (it still works), and it seems to fit into the “it just works bucket”. Good price point (especially if data transfer is a worry for you), fast NIC speeds (getting over 100Mbps is challenging at this price level), ability to deploy images, a fabulous reporting/monitoring engine – Longview. And an API. Nobody should be touching anything that doesn’t have an API that you can do everything you need to through.
I do not, and have never, worked for either AWS or Linode, but they both have been wonderful providers to me and my clients time and time again.