OK, here are things that you should consider:
How many servers are they running?
Where is the datacentre? (Out of town DCs are more secure)
What vendor is supplying the servers?
What is the contention ratio of sites to servers?
Do they offer the flexibility to move between hosting plans as your requirements change?
What technologies are they offering? I.e. PHP vs ASP, MySQL vs Access?
What OS are the servers running?
How many comms links do they have? (1 is not enough)
What is their backup policy?
If you're going to pay for your host, you might as well get serious about specifying your requirements, and only then make a decision.
This is my host, I'm very happy with them:
1&1 Internet