I don't have experience with Hostgator's VPS, but their shared hosting had been fine for my needs for 7 or 8 years now.
As for VPS, I've only used a fully managed VPS from Liquidweb, and it was great. Back when I purchased it I found a coupon at webhostingtalk.com, which gave better specs and a lower price.
If you're a well seasoned server admin, you could go for an unmanaged VPS - it will surely come with root access. I seem to recall that Slicehost and Linode were getting good reviews, but this was a while ago, and I never used them myself.