1) Get a dedicated IP. If the host doesn't offer that (and these days most do), find one that does. And this is only a safety measure. Not sure any more that it makes much of a difference. Certainly there are lots of thriving sites that are not on a dedicated IP.

2) Avoid hosts associated with spam. This is easy to do. Most people complain about the difficulties in finding hosts. I have a list of hosts to try I haven't even got to yet. Just go find a bunch of high ranking sites and see what hosts they are using. Also, see if the host is well cited around the Web. The host won't have a darned thing to do with any of those sites' high rankings. You'll simply know that those hosts did not *prevent* the sites from ranking well.

After that, it's all down to up time/reliability, costs, and whatever specific issues/needs you might have.

One more thing. If you plan to send out a lot of email soliciting links, make sure you find a host with a policy that is not too harsh in that regard. You don't want to have your site shut down because of a single complaint based on a polite hand written email.