Which hosting provider would you recommend?



Hostgator is great. But if you don't want to go that route, I second JustHost. If you do not want to pay up front, you can go to webhostingtalk[dot]com to find really cheap monthly hosting options. Hostgator has a month-to-month option but it can get fairly expensive.
 
I'd recommend eUKHost too. Great support and very few issues over the years I've been using them. Also use Hostgator without problems.

Whatever you do - don't pick just based on price - saving a few bucks is not worth the hassle of crap hosting.
 
get cloudhosting in case you are just starting.. get VPS if you are serious..

ixquickweb, amazon, rackspace, vps.net, vpsnet.com etc

Lunarpages SUCKS, godaddy sucks, host-one-plus sucks Ass, bluehost is ok (for low visitor sites), hostgator = same as bluehost

all mentioned above are based on personal experience (yes I've moved around)
 
Bluehost and Hostgator are good for hosting your site. I use Hostgator. But I hear Bluehost is equally good if not better (basically, these are in the same class from what I understand, as of now), and certainly it is cheaper (going by the prices listed on the sales pages).