Here are some things to consider when selecting a Service Provider. I'm assuming that you're looking for a provider for a solid business relationship for an extended period of time.
If you're using a formal Request for Proposal (RFP) process, I suggest a two step process. First identify those interested in offering their services and that meet your minimum criteria. Then spend time interviewing, investigating and following up on your short list.
The following list of questions and concerns is mostly for evaluating local and regional providers. Larger national providers will often either give you boilerplate or simply ignore your requests for some of these details.
Do they have the equipment and software necessary to do all the things you want your site to do? Walk through your features list to be sure.
How's their connection to the net? Try out some of the sites they host. Ask references if they're satisfied.
Are they financially sound? Many smaller providers were started by folks with limited capital or poor business management skills or both. I recommend running a routine credit check on the candidates on your short list.
Do they have the expertise, equipment, software and procedures to provide adequate security? I suggest you get help evaluating this one. You should expect your provider to have firewall and intrusion detection software, to respond to security and software advisories in a timely fashion, and a program of background checks or bonding for people with access to sensitive information.
NOTE: I find that many local providers get offended when you bring up the screening issue. You will have to decide how hard you want to push on this.
Do they have the equipment, software and procedures to detect and deal with service problems? Ask them: "If it's Sunday afternoon and my site goes down, how will you know and what will you do?" Then see if you like their answer.
Finally, do you feel comfortable dealing with these folks? It's a long term relationship that you're after. You should be comfortable with your partners. If you're not, don't tie the knot.