Full Disclosure: I work on OpenStack.
These days, there is no functional difference between cloud providers, there's only a strategic difference. Each of the providers have figured out how to maintain basic compute and storage nodes, which is all you should ever need to use. Why? Because of vendor lock-in.
As soon as you sign up for one, it's going to become very easy - and very financially attractive - to start consuming packaged platform-as-a-service offerings from that cloud. For instance, using Amazon's Kinesis is cheaper than running your own Akka cluster on provisioned nodes. The downside is that every time this choice is made, you're choosing vendor lock-in, and suddenly you've agreed to the often-debilitating pricing tiers offered by all providers.
If, instead, you choose to spin up your own nodes and manage your own clusters, you are no longer tied to that cloud. Migrating to other clouds can be as simple as opening up a VPN bridge to your new data center and linking your replication across that channel, and with tools like Ansible, the only thing you really need to worry about is: What operating system is going to run on your nodes?
The only remaining hangup is likely whether your service needs to provision nodes for your customers, because in that case you have to build towards the underlying API. If this is not a problem for you, I would say: Select on price, select on uptime, everything else is fluff as long as you provision your own nodes. If this is something you want to do in the future, then I would personally recommend any of the OpenStack providers (Mirantis, Rackspace, Redhat, HP, Canonical, etc). The reason is not only that there's more competition in that space- though there is, and that only benefits you - but because you have the ability to ditch them all and spin up your own OpenStack cloud, with no licensing fees, and migrate to your own hardware.
Also, speaking from personal experience, the line of "Oh that's less code for your engineers to figure out" is usually bull. Connecting to MySQL is just as simple as connecting to Amazon's RDBS, and the nuances of PaaS implementations are just as complex as learning the underlying technology. The only "additional overhead" is on your sysadmin, and he/she should already be an expert at setting up these kinds of servers anyway.