Jeffro, I had a similar problem with Bluehost, which sits under the same umbrella as Hostgator. One of my lowest traffic sites just took ages to load, sometimes as bad as 30 seconds to load a majorly text page. This performance was bad inspite of using CloudFlare on the site.

They gave me the usual, improve performance of WordPress and move to a premium plan. After nearly a month of frustrations, I shut my account and moved this site to my VPS.

I can't see how it could have been only WordPress related and not the servers. I have a feeling certain optimisations they did on their servers caused many sites to load slower (had a high wait time for each request).

Regarding related posts, a simple pitch for my plugin Contextual Related Posts. In the latest version I added caching support that caches the output HTML directly in a meta field so there are no major FULLTEXT database look ups to find new posts after the first page load.