mm, <a href="http://www.slicehost.com/">slices</a>.

Never dealt with hostgator, but anybody with a million plus domains is going to get bad feedback. It's when you host ten domains and you have 8 people complaining that there's a problem.
-m