+1 - Nothing like being able to show a client who's got a billion dollar idea that his site can handle 10M users for $15/mo.
Just remember to explain all the caveats that are being discussed here. We're nothing without out integrity. Your client won't be listening to that point though, he'll only be excited he's going to be a billionaire for $15/mo.
Linode has always worked very well for me. You do have to have some basic Linux sysadmin skills, but they have good documentation that should get you on your way, awesome support and it's way cheaper than Heroku or Gondor. So my advice would be: Linode combined with EC2 for storage