Are they related to the old Gator spyware folks? If not, it is an unfortunate choice of name.
My experience with Hostgator is that they provide solid shared Linux based hosting. I doubt they have anything to do with the awful Gator spyware.
I’ve also seen good performance from Imhosted.com. They seem to have very fast server connections and performance, for around $6.95 per month.