I personally think that the best place to advertise a hosting company is on webmaster forums and word of mouth. I see that as the best because you are getting out to the people that are going to need hosting, so it works in your favor.