This is a monster of a question. Frankly, your choice of "cloud" provider is nowhere near as interesting as the architecture of your application. If you're unfamiliar with the mechanics of coding a large, scalable app, I would recommend going with one of the far more restrictive providers such as Google App Engine (if you want to write for one of the frameworks that GAE supports -- mostly Pythony things, I believe) or Heroku if you want to write in one of the frameworks they support (most of the Ruby ones).
The reason I recommend this is that providers like these have worked out a set of technologies they're comfortable scaling up, and as long as you use those technologies, they take away a lot of the architectural pain. If you sign up with EC2 or RS, for instance, you've got to work out how to load balance your app and deal with increasing and decreasing resources yourself, whereas these more "managed" providers deal with all that sort of thing themselves.
The big downside to these providers is that if you want to do something that they don't support, you are largely stuffed. They don't have the flexibility to be able to provide you with, for intance, a different data storage methodology. If you were to find yourself in that scenario, you would need to be managing your own infrastructure to be able to incorporate those components. I'd learn the limitations of your chosen provider well in advance and make sure I architected my app to avoid getting into that situation. Moving away, if you need to do it, is going to take a lot of time and effort from people who really know what they're doing (and cost big dollars) to get right.
One advantage that Heroku has over GAE, in my opinion, is that GAE has a pile of "Google-only" components that you just can't get or use anywhere else, while Heroku uses all OSS technologies in the bits that matter, so moving a Heroku app somewhere else is relatively straightforward, whereas if you're tied to Google technologies, you're totally screwed if you need to move.
