Hit up the local market first as it seems you are planning. Then once you'd established a solid foundation of local clients, begin to spread out and perhaps put some of that money into advertising on a few websites. Since you are a new company, I'd suggest that you stay clear of the hosting forums and related websites where you will see loads of other host companies advertising. You're not going to compete to well with established companies at such an early point.
The niche idea is a very good one. Try to find a different point that maybe other hosts don't offer. I currently do technical support for a company that only caters to the open source community. He's built quite a sucessful firm by catering to the CMS crowd and not just being another face the in the crowd.