I've personally moved customers from both Hostgator and Godaddy because of their terrible hosting. Bad support, provided by people without basic knowledge of running servers. Anything but those two.
I recommend posting on
http://www.webhostingtalk.com/ or similar forum. Its full of representatives from different hosting companies. Just say that you want XenForo, they'll make you nice offers. It is also good for checking if host you are about to signup is any good.