Hosting directory -- way too many web hosts competing, and if your budget is tight, chances are your ad will be small and will be amongst the flood of other web hosts.
Target a specific market -- say, people who are looking for a host for their blogs, or photo albums. Then look for web sites that cater to these kinds of people. Advertise there.
Advertise where other web hosts aren't advertising. (hmm... what a concept)
JP