Question: Why would you register with your host with all the advise here to NEVER do that?
Okay, too late for you but you could appeal to your region's controlling registrar for transfer the domain to a responsible registrar while you're searching for a reputable host.
I offer my common advice:
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!
2. 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.
3. 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.
4. 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.
5. 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.
6. 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).
7. 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.
8. Finally, you'll have enough information to make an intelligent selection.
Been there, done that (all too frequently in the past).