I thought HostGator was okay - nice to have an update on the service they're providing!
I've gotten upset at hosts over time and have used this process to find a new host:
[indent]1. Establish your requirements, i.e., Linux, Apache 2.4+, PHP 5.2+, MySQL 5+ and storage and bandwidth requirements. Remember to allocate for log files, databases, e-mail (attachments) and growth.
1a. (added) If you're looking for a VPS or dedicated server, remember to ask what the host's managed services provide. Remember, a non-managed host must be monitored by you 24/7/365!
Know what control panels you are willing to use, i.e., WHM/cPanel. cPanel is the standard bearer for Linux systems and Plesk for Windows systems.
Know how much CPU time/RAM you need. If you need a lot of processing power (like Zoomla and other CMS's), this will be a major factor. These, however, are usually specified only for VPS/dedicated accounts and automatically throttled for shared/reseller accounts.
Know your target (the Internet is fast but some latency could hurt so the closer your server to your target audience the better) location and try to host as close to your target as possible.
SEARCH (using the above parameters) recording each feasible host as well how well it satisfies your requirements and budget. Spreadsheets are good for this as you can assign weighting to the different requirements and how well they were met to generate numerical scores.
Create a shortlist based on the database you've created in step 5 then SEARCH for comments about the host (avoiding obvious shills and websites which advertise for that host).
The last step (other than selection) is to contact each shortlisted host with a question (I've used .htaccess and mod_rewrite availability, which services are managed by the host, the availability of IP addresses - you will require one for each SSL you use - or ask to test proprietary control panels - they may make life too difficult for you) and record the response time and your level of satisfaction with the response.
Finally, you'll have enough information to make an intelligent selection.
Been there, done that (all too frequently in the past).[/indent]
When you get a new host (I use WebHostingBuzz and WebHostingZoom [but they're getting very slow responding to problem tickets]), I'd recommend:
Transfer the accounts via cPanel/WHM. That should transfer EVERYTHING and eliminate many of the configuration tasks of opening a new hosting account.
Get help (if you need it) to configure your EXIM to send SPF and require senders be associated with individual domains. The IP address problem will go away and should not return with careful configuration. VPSs get their own IP Address so don't let it be abused (hackers as well as your own accounts - keep your sites safe by using good coding practices and VERY strong passwords.