Hi OP- might I recommend that you use Cinfu.com?
I just bought a domain from them but of course they do hosting and private servers as well. I used them because they accept Bitcoin... and the transaction was very easy. I have a few dozen domain names at GoDaddy... I've always used them, but I may just migrate them to a new host like Cinfu because they accept the good coin

I can second this. I currently have a (hidden) IRC hub running on a Cinfu VPS (their smallest plan) and it's been very reliable so far. Payment (in Bitcoins of course) was also very easy.
Another one to recommend is Ramhost, even though they do not accept Bitcoins (yet!). I have no experience with their shared hosting, but I've heard good things about it, and I've been a happy VPS customer for over 1,5 years with them now (currently have 5 VPSes with them of varying specifications).
Also joining in on the rest: no matter what you do, stay away from GoDaddy. They fall in the same category as LunarHost, BlueHost, Hostgator, and all these other hosts like them. They are known for aggressive marketing, unreliable services (reliable enough for a weblog, but not for anything serious), varying customer service, and more than once I've heard people complain about billing issues with GoDaddy hosting.
As far an Amazon instance, you will have to set up a webserver yourself... I am not sure how Amazon instances work, but assuming they work like regular VPSes (and run Debian) you can simply google 'lighttpd php mysql debian' to get a tutorial for a fairly simple webserver setup... you may want to have someone who knows how to use Linux help you with this.
Can you describe the kind of thing you want to host more specifically? It helps if people know what exactly you want to do with the hosting
Also, stay clear from any host that offers you unlimited disk space or is otherwise offering things that seem too good to be true. While hosting can be cheap (look at Ramhost and Cinfu), these 'screaming marketing' websites are usually this aggressive on marketing for a reason, and try to lock you into a 1-year (or longer) hosting plan. I believe both Ramhost and Cinfu offer monthly plans where you can cancel at any time. "If it looks too good to be true, it usually is."
For those wondering why unlimited disk space is bad... when was the last time you saw an unlimited harddrive in your local electronics store?