It depends on your growth prospects. If you're not going to have 10,000 active users from day one, I'd stick with something cheap and simple like slicehost. It should last you a surprisingly long time and save you a lot of annoying configuration.

I just went through scaling my app for EC2 and it took a good week to get it all worked out. By comparison, setting up one instance on slicehost takes just a couple hours.