HostGator is okay, I personally canceled my account because of their ssh and file permission restrictions. Plus, I had a run in with a pretty stupid "tech support" agent.
I also hear good things around the vBulletin support forums about SiteGround, although I have no experience using them.
What about v7n hosting? This is a pretty big forum and it flies.. If the rest of their servers are this fast, I'd jump on a hosting account with them in a heart beat.
If don't mind spending a little money, VPS is the way to go. I have a VPS with
ServInt and highly recommend them. I recommend them so much, I won't cheapen myself by trying to slip an affiliate link past the mods.
@Jason: I got your PM & replied.