Hiya
The first thing I look for when checking out any new hosting solution is whether or not there are public support forums. If the host doesn't have them, there's no way they will get my business or my referrals. The bottom line is if they hide support issues from their community, they have more problems than they are willing to admit. It's one thing to say you've got great support, it's another to actually show it!
Next, I check those forums for information. If you go to a place that has 100 people screaming about outages without replies, I think you're getting a good idea about what the company is like.
From there, I look at the server concerns.
1: Connectivity ('Net backbone Level 1, 2 or 3 T-Comm Service Provider?)
2: Connectivity (ATM, T, Frame-Relay or other connectivity & Provisioning of each segment)
3: Connectivity (Redundant Links?)
4: Connectivity (7x24 Monitoring? and by whom?)
5: Connectivity (Measured %Uptime for last year)
6: Connectivity (LAN & Uplink connectivity... Layer 2 or Layer 3 or 2/3 or other?)
7: Server construction (See below)
8: Who built the server? (Am I potentially going to Dell Hell?)
9: Location (Is the server in a potential disaster area?) This is my business, the last thing I want is to show up at a disaster site and find out my (or a customer's) server is in that city unless there is a redundant server somewhere else.
10: Who is the company providing the hosting and are they going to pass the scrutiny of security & credit checks? I don't know about you, but I'm not about to give business to a company that writes bad checks... or that has been busted for hosting Child porn.
11: Garantees (If I go down for a day, I better be seeing a credit)
Server Construction Details:
Customer Allocated Disk Space & Customer Allocated Bandwidth (Monthly) (These two issues are price/performance comparison issues)
CPU(s) (Prefer dual Xeon's but will look at others)
RAM (Registered ECC CAS3 1 Gig min?)
Drives (and RAID construction... I only use/recommend HS SCSI systems)
Linux Version (Brand, Version, Build)
Apache Version (Build)
MySQL Version
PHP Version (CGI or Module, Version)
PERL Version Information
Cpanel/Plesk/Ensim Panel Information
Add-Ins, etc...
I have designed and built thousands of Systems and hundreds of Networks for the high quality minded organizations and Government agencies so my standards tend to be much higher than the average Joe. Basically, I'm looking for quality over price or quantity.
I've also been on the bleeding edge with most of my own design work so I've had much experience with understanding the differences between Frame and Cell communications (for example) as well as understanding WHY these are important issues depending on your needs.
People that look for discounted, shared hosting generally don't care about these issues until there is an outage or their performance is like dial-up. Unfortunately, not doing your homework up front, usually means you've wasted time and money finding out about these things later, when it is too late and you'll just end up doing it again. The other downside is that there are a million shared hosting solutions, but only a very select few are any good.
You asked....

Hope this helps and answers your question!