AWS is excellent. You can use the free tier for the first year, and after that you only pay what you use. It's highly scalable, so if your site/app usage explodes overnight, it won't be a problem. Shameless plug: I wrote a tutorial on how to set up a LAMP stack on AWS a while ago:
http://www.dirktheman.com/tutorial/setting-up-your-lamp-stac...