First off - what are your USPs?
There's so much competition in this industry that without proper specialisation (and offering something that others don't) it's virtually impossible to compete - even if you have a 6- or 7-figure marketing/advertising budget.
Just take a look at WHT - there's literally 10 new "hosting companies" (most of which are obviously one guy who bought a $20/mo reseller package or a $30/mo VPS from some other company) popping up every day, offering dirt cheap prices (it has always amazed me how these guys can manage their accounts and pay their support staff, let alone pay themselves) so really it's one of the worst industries to get involved in ....... unless you can offer something that others don't.
So first of all, before thinking about advertising avenues and spending money on marketing, try figure out what separates you from others OR find a niche/group that's easy to sell to and that competitors haven't spotted (yet).