Hostgator is pretty nice usually, but it really depends on what features you need and your budget.
I agree, I’ve had a good experience with them over the years as well.
For registering domains I hear they’re decent, and I used them as well many years ago with no issues. For shared hosting though, I would definitely recommend steering away from them. Server performance was among the worst I’ve seen, though, surprisingly, uptime was not all that bad.
Then if you can’t afford downtime exclude cheap from the idea.
You can take a look at micfo.com or knowhost.com to see if they suit you.
Id check out the review places here on this forum or at other forums, always research the host your going to go with.
just check at this forum : http://www.webhostingtalk.com/forumdisplay.php?f=4, i think you will confuse to choose 
I have tried many, hosts and my favorite is ICD host. They are super fast and I have had no downtime with them in over a year. One thing that really surprised me is that they offer gzip on all of their hosting packages. Definitely the best shared hosting that I’ve experienced so far.
Why you are looking for cheap? You won’t really get one if you go by cheap, you have to pay for the quality.
Pay less get less. You can also start with free hosting but … is your choice.
I’m sorry to intervene on a thread that seems to be resolved but I’ve had several BAD issues with “Hosting Zilla” to include personal information leak, high amount of spamming, frequent and unexplained downtime and billing issues. Think twice before going with them. That’s my two cents.