There are many articles and white-papers on this topic. I just want to give a brief summary of thought process one has to go through before selecting a Cloud Service Provider. Also, I will not be explaining what SaaS, PaaS and IaaS or Private Cloud here. This is based on my hands-on experience, my analysis of the landscape and knowledge gained from numerous articles on the web.
First thing to decide is which cloud model to go for. If we need to perform a non-core function such as payroll, CRM etc go for SaaS. Leave that to the experts. If we are doing an application that needs very high performance and scalability requirements then go for IaaS. Ex:- a payment processing system that has to respond in a second or a high traffic news website. If your nature of business has to follow some regulatory requirements such as HIPAA, that data has to in Private Cloud(best option, though you could still find some IaaS to do it with a specific SLA).
Now for the rest it really comes down to architecture of your application and if you have some code already present or not. If it already has something working and it doesnt use any standards based coding then one has to pick IaaS. If one is starting form scratch and wants to leverage the platforms developed by the PaaS providers they will choose PaaS. Even though that will reduce time to market by a large amount, one has to be thinking about the lock-in. Sometimes one maybe locked into the platform. Using PaaS will give some out of box features you do not have to write code for(like some social networking libraries or mobile platforms). A new open source standard is just out called cloudfoundry. That will actually help PaaS to move accross vendors easily. So how important is for one to move between service providers is the last important thing to think about while picking a cloud model.
Another important thing is to check their SLA for their uptime guarantee. Providers like Amazon EC2 will even give you options of reliability. If your company is new and not many customers are present, you can choose the cheaper one with slightly less uptime guarantee
Another factor is the pricing model. Will you be charged per instance or per usage. If you are a new company, you would prefer a vendor that charges per usage(pay-as-you-go) and not per instance configured. That will put the costs low and there would not be any commitment charges.
The next factor to look is Elastic Load balancing availability? This becomes very important when your application becomes a hit and you have to scale for many users. PaaS providers normally always have it. For IaaS providers one has to see available options and pricing models.
In addition to that, one has to see if the service provider is providing tools to monitor the health and also be able to control/diagnose them. Some vendors have automation features and they are very useful. Ex:- If CPU utilization % is greater than some configured value, you could be able to fire up another instance etc. Some vendors provide only tools to monitor and configure but not diagnose in case of issues. Some even have mobile apps to control and manage the services on the road. We have to understand our needs before checking that factor.
One need to be able to pick a vendor from which you can always migrate to a different vendor very easily. One can also have two instances running on two different vendors and one can act as a spare. So if anything happens to one vendor resulting in downtime for the application, shifting to other vendor is very easy. Spare becomes relevant only if we choose a not so popular/reliable vendors to save some money.
Some Vendors provide Linux or Windows instances and some provide you direct virtual machine instances. If it is direct virtual machines you might have more flexibility in choosing your application's building blocks. In addition to that, you also have more freedom in moving between vendors is straightforward. All one has to do is pick a vendor in the list of vCloud partners.
Last but not the least is Security. One can ask the vendor a list of questions such as, who has access to servers, database and what are their disaster recovery procedures etc. If a vendor is not ready to provide the security and access logs, then their overall quality becomes questionable.
I hope that for someone looking to pick a cloud vendor for their business or startup this write-up will set the mindset in the right direction.