Alot of people will scoff at this but I had good service, well over 90% uptime, and very few errors over the seven years I used shared hosting with godaddy.

I'd say check out http://invokevm.com they have great prices and the support will bend over backwards to help you.

I have had hostgator since 2009 but after they got sold to EIG performance is not the same. They have recently been wanting me to upgrade from shared hosting and I never had problems in the past on shared hosting, their customer service is nowhere near what they used to have and they always blame me or the scripts instead of admitting something is wrong on their side. This will be the last year I stay with hostgator unless they improve which I highly doubt they will.

But yes, this is something server side ...

Ditto.
They even started locking up my forum with the reason "to many processes running". I had no changes to the forum for years.
Also I had those "SQL server gone away" errors suddenly over and over with them.

Switched to URLjet. Not the cheapest but very reliable, fast and great customer service.