Hosting all round seems to be pretty much a lottery until you're up into the realms of dedicated boxes with Rackspace for a few hundred per month.
Before I got to that stage, in the last year I've put black marks against the following:
1and1 - don't believe the hype, regularly goes down, and their support team won't tell you anything you don't know already. Cheap as chips if all you want is a blog to host pictures of your cat on though.
Heart - not bad in terms of uptime, just dog slow most of the time, very cheap though, OK for lightweight niche sites.
Pipeten - worst of the lot, - pulled a live eCommerce site in what I can only describe as a 'strop'. As soon as that site's moved the contents of the chat with their 'support' team is going on my blog.
If you just want something cheap, I have a VPS with Eukhost who have been very good to me, there have been some problems but you can get someone on a live chat session in seconds at any time of day and they are genuinely helpful. If they can maintain standards they get my vote. However, I've seen other golden boys on this forum go down the pan in less than six months

. I based my
Affilistore tutorials last year on their hosting.
It seems that getting through these problems until you have the funds for decent hosting is just one of the challenges of getting started. Everyone you talk to has a similar tale.