If you are interested in systems administration. I would go with Slicehost, Linode or AWS ec2, Linode has been shown to be more performant (link) than both Slicehost and AWS.
With that said, if you aren't interested in systems administration I would go with Heroku. It is the easiest way to deploy and management is minimal. You do have to be aware that Heroku is limited on some 3rd party services you would install on your own, but but they do have some packages included that you can enable for sending email etc. You are also limited on file size and they recommend you store your assets on AWS s3.
In terms of overhead Linode is less than AWS ec2, because AWS ec2 is really for high availability, Heroku is the least as mentioned above. AWS will cost you more than Slicehost or Linode and I think if your site is small more than Heroku too.
You will need decent Linux chops to get going on AWS, Slicehost, and Linode. Heroku will keep you away from most of this but also limit you if you need something really custom. For distro choice I would say Ubuntu hands down if you are new.