First of all you need to consider if what you need is very basic and will not require a high SLA or the ability to grow with usage you are probably better off choosing a virtual private server provider. If you are fine with a Linux box these can be had extremely cheap. I used to be a customer of Letbox and at the time they provided me with a Virtual Private Server for $5/month, a price that is hard to beat. It is however important to realize that this is not a true VM, it is a specialized version of Linux similar to doing a chroot but also with quotas on memory and CPU usage. This means that these VM:s can only run Linux. That said the price is simply in a league of itself, cheaper usually than even spot instances of AWS EC2.
However once you have something slightly more complicated to run you probably want to go with a "real" cloud provider. These come in two kinds. The first level are companies providing infrastructure as a service (IaaS). This means basically providing virtual machines, storage and networking for them. It is up to you to build everything you need to run off of these primitives. Companies that offer only this kind of computing includes Skytap, Rackspace (Although Rackspace does have some platform services) and many more.
The next level up are the companies that provide platform as a service (PaaS). All of these companies also provide the infrastructure as well if you need it, but on top of this they provide useful packages that they will run for you as managed services to help creating, deploying and running your services easier. These minimally usually include.
- Load balancing of traffic to multiple servers.
- Auto scaling of new servers to handle varying load.
- A fast and scalable NoSQL key value store.
- A managed transactional database.
- Web hosting.
Of these Amazon is by far the largest. AWS started out as a mainly platform as a service offering, but now has one of the most complete set of managed services and they have by far the largest set of data centers located all around the world and one region qualified for US government work loads (Having an account on it requires you to be a US citizen so I can not use it). Their infrastructure is truly top notch, but their development tools are not great. Only a few languages have an official SDK (I myself have been missing an SDK for PERL).
Microsoft approached this space from the opposite direction from Amazon and started out by offering specific platform solutions and tightly integrating the development and deployment of Azure applications into their development tool Visual Studio. It is the only cloud provider I am aware of that for a time did not provide IaaS at all (Although they do now). The SDK and tooling for all of their products is truly excellent, especially if you are a .Net C# developer, but many other languages are supported as well. They do unfortunately and understandably run most of their infrastructure on Windows which simply is not as solid as other hyper-visors out there and if you are building a solution that requires reliable quick processing this can be a problem, especially if you have a cluster of synchronized machine this can become really problematic. These synchronization issues usually only occur a few times a month though as the service is migrated to new machines as all the VM:s running the service undergo the monthly Windows patching. However as long as your application does not rely on tight synchronization between several systems you are unlikely to notice it.
Finally there is Google. Their solution is similar to Amazon something that has grown out of their own business and they have several offerings that are obviously simply surfacing of their internal operations like for instance Big Query. Google's infrastructure is fantastic in regards to reliability and performance. They do though in my opinion offer the most narrow platform solution of the big three. What they do provide though is truly top notch, and they are also priced accordingly unfortunately.
Price wise the big three are relatively similarly priced. If your application can take advantage of the AWS spot pricing you can get away with really cheap solutions though. Google is usually the most expensive (I say usually since the prices change all the time for cloud services). One thing that could be worth investigating is if you qualify for a Microsoft Bizspark membership because if you do you will receive $150/month of free credits to use for almost anything in Microsoft Azure (And it also includes licenses to almost every product that Microsoft has in their very extensive portfolio).