Michael's answer is great, Ori.
One major consideration is the data side of things. Compute resources are relatively cheap, and you can scale them up and down to meet need. So start with a couple of m1.medium instances, perhaps, and see how they fare based on the needs of the application.
I large site I run on AWS uses about 12 m1.large instances running PHP, processing about 1000 API calls per second to mobile apps, just to give you one concrete measure of scale. And I wouldn't say it's particularly optimized, it's doing quite a bit of work per request.
But the database is where things get tricky. Both because you need additional redundancy in a way that you don't with the application servers (essentially two copies of your DB, Multi-AZ RDS, or whatever is equivalent for you). And because the database typically can't scale up and down with traffic. So you'll end up paying a bit more than you need to at the beginning out of fear of not having to shut it down to resize every time you hit a new capacity threshold.
Most small companies (< 1M users) don't do any sort of auto-scaling (meaning, spinning up and down resources during the day, so you have more capacity at peak hours and less over night), but if you really are trying to save cash, you can go that route. Typically, the developer resources to build a stable effective auto-scaling solution aren't worth it, unless you get it "for free" via another platform layer (like parse.com, rightscale, etc.)
But heed what Michael says, don't worry too much about scale early on. Spend more time making sure that your mobile application is flexible, well-behaved, can take behavior hints from the server, has the ability to enable/disable features of the app remotely. That stuff will buy you flexibility to scale server-side as your needs demand.