I've had great success installing cPanel on a Linode, (Xen) and with the recent increases in resources in their plans, you can buy a $20/month Linode plan with a $15 cPanel license, and get super duper performance without having to relearn everything.

Your site loaded really slowly today. Hostgator isn't very helpful. Actually, what you got from HostGator is the most helpful I have ever seen them, they're usually defensive. I guarantee you will never get to the bottom of it.

A friend who uses HostGator that just got relocated to a new server because of a major hardware upgrade on a shared plan and it made things better. If you didn't already get upgraded, ask and see perhaps if they can relocate you ahead of time? (They got NO notice of the move, just fyi.)