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?I want to make a game that you can bet btc and pick a number from 1-3 and you win back double it would use bitcoinbalance.com if the owner emails me back for withdrawals and deposits.
Okay. I'm not entirely sure how BitcoinBalance works, this is probably a question you should be asking them (BitcoinBalance). My guess is going to be that you will need to use cURL.
I'd just wait until you have a response from BitcoinBalance as to what the requirements are to use their system (specifically ask for any PHP extensions that may be needed).
After that, you can decide on where to host it. If it only requires something like cURL it would probably be best to go with something like Ramhost shared (you should ask them if they have cURL support beforehand though). If you need to run any specialized software, something like a free Amazon instance may be an option - but be aware that if you use an Amazon instance, you will have to learn to set up and maintain a server on your own.
As for the pricetag, Ramhost's smallest shared package would be enough, and is $0,75 per month (you pay per year though, probably because of transaction costs, so that would be $9 for a year of hosting). That wouldn't include a domain though, so you'd have to get one elsewhere (at GoDaddy, or Internet.bs for example) and just point it at the Ramhost nameservers (which is 5 minutes of work). Total pricetag would be around $21 for a year for both the hosting and domain, assuming you'd get the domain at GoDaddy.
EDIT: Best to not order anything before you are sure about what the requirements are... so I'd just wait for the response from BitcoinBalance first.