1) security (is your server/software safe?) 2) technical support (can your hosting company help you ?) 3) backups (do you have _any_ backups of your data ?) 4) quality of customer service (does your hosting co treat you good ? this can become very important) IMHO
Support and Backups are most important for me. Once your site becomes a mega-site, you have to rely 100% on your host for backup. Also if I have a huge site, I will only host it with established hosts...you never know when a smaller player may go down.
I always look for 24/7 support in case something goes down, DNS server, etc. Also backups and a good fire supression system ease my mind. But mostly will the server handle the load I expect to put on it? If you have lots of MySQL queries and processor/memory intensive stuff, will it handle it? Send the host an email and ask what the default configuration is of MySQL. Most hosts don't optimize it, so even medium-sized sites get bogged down with the server not being able to keep up with the sql queries.
Uptime is crucial for a big site. At least 99.9% or else you will lose customers. Then speed of course.