I guess it depends on how much traffic you're going to be successful in driving there and how configurable you need the hosting to be. Obviously with Amazon you can put anything you like on there, but if your needs are less exotic, then going with a Slice Host of sorts or any really cheap annual hosting will do the trick because they come with what you want without the need to configure or backup much.
You could even host it on the Google App Engine for free if your python skills are up to it... and there you shouldn't have the trouble of scalability or cost.
Personally I think running it on the Amazon or Google Cloud is the right answer here if you're serious about it. Mainly because it's a pay for usage model. If your product marketing turns out to work well, then you'll have more traffic, and the Amazon hosting will only then start costing you more, but it's still pretty cheap at that. Google let you do it free until your app creates enough traffic to be noticed...
Hope that helps!