In my experience, a single person ("John Smith" or "John Smith Consulting LLC") isn't at a big disadvantage against a small company (John Smith as sole member of "Razor Consulting LLC" or whatever). We would often compete with, and work alongside, individuals. It's all about getting your brand out there. You want people to hear about and trust your brand - whether it's your name as an individual, or a company name. But don't confuse people by pushing both. I actually recommend using your individual name unless you want to grow bigger than 2 full-time employees. I have several friends who are individual contractors, and most of them have incorporated under another name. But they are known by their personal name, not their company name. That's their brand, so to speak.
I know 10-20 independent programmers and designers in my area, and in every single case, I think of them by their personal names. I'm sure they all have some LLC name, but in most cases, I don't know what it is. Even if they put it on their business card, I'm more likely to refer them to someone as an individual ("I know this good designer - Mick Jones - you should talk to him") rather than by a company name ("I know this good design shop - Compelling Solutions - you should check them out.")
I think this changes when you grow beyond 2 full-time folks. At 2, people can remember both of your names. But beyond there, they're likely to remember the company name, plus one of the principles. ("You should check out Compelling Solutions - talk to Mick Jones.")
At least that's my experience. :)
I guess it's a lot easier if you push yourself as an independent programmer, as it's reasonable that a single guy is already busy at the time you call him... but as soon as you introduce a company name I think the expectations change. So that's an extra reason to follow your advice.
Relationships, on the other hand, can be built quickly. The best relationships for us were relationships with other developers. We've gotten dozens of good leads this way, and have passed out dozens to other developers. What technologies are you going to use? Local user groups for those technologies can be a great place to start. Figure out where the local momentum is (Ruby? Python? User Experience? Startups?) and meet people.