One thing to avoid: over the years, a lot of hosting companies have been purchased by a firm called Endurance International Group. Unlike most companies doing acquisitions, they make a big effort not to publicise the takeover or ever merge their brands. The MO seems to be "even if we make the service suck, odds are many of the customers who leave will end up buying into another of our brands."
They bought out Bluehost like a year ago. We had several client sites there. Since the takeover, it went from "simple trouble ticket like installing a SSL certificate takes 30 minutes" to "ticket takes 3 days" to "ticketing system is disabled, you have to sit on a livechat for 30 minutes to even ask for support". They rolled out a caching system, which breaks sites that aren't expecting it (it would serve cached versions of pages that we expected to be regenerated on each load).