There were a few things I looked for when I was switching hosts last time-
Uptime & reliability. This was first and foremost.
Control over our server. Because I was toying with the idea of getting a dedicated server, but I didn't have the time to hassle with it- I was lucky to find a webhost that let me control (to a point) what was on our servers, schedule cron jobs, set up databases, block IP addresses, that sort of thing. It's as close to having a dedicated server as you can get without worrying if the server will go down at 2 am.
Price. While we were willing to pay a little more for a high quality web host, this was one of the primary reasons for us switching in the first place.
Support. It's good to know that if there is a problem, there is someone somewhere working on it 🙂
[edit]Our current hosts offer unlimited emails, databases and 1000Mb space with 50 gig transfer[/edit]