A marshal dip when you already have Skill Focus (Diplomacy)
The marshal from Miniatures Handbook gainst Skill focus (Diplomacy) as a bonus feat at 1st-level. Unlike every other class feature offering a bonus feat, the marshal’s class feature reads
Skill Focus (Diplomacy): Because a marshal has a way with people, he gains this feat as a bonus feat. If the marshal already has the feat, he can choose a different one.
So you can take Skill Focus (Diplomacy) ahead of time, and then dip marshal when you need Primary Contact and get it as a bonus feat. Note that, since Primary Contact itself requires the Favored feat, you also need to take that feat—so two feats and a class level burned on this trick.
Frostblood orc or half-orc and Endurance as a bonus feat
Kind of coming at this from the other angle, the frostblood orcs and half-orcs from Dragon Magic gain Endurance as a bonus feat, again with some unique wording:
—Endurance: Frostblood orcs and half-orcs have Endurance as a bonus feat. If a frostblood orc or half-orc would later gain Endurance as a bonus feat, he can select any other feat for which he qualifies.
So again, by being a frostblood orc or half-orc, you can gain Primary Contact as a bonus feat instead of Endurance as a bonus feat. The trick is timing things so the bonus Endurance feat lands on the level you want. Notably for prestige classes requiring 8 ranks, a mystic ranger from Dragon vol. 336 gets Endurance at precisely 4th level, perfect for early entry (simply dipping something else to take ranger 3rd at 4th level works for too, of course). The pugilist fighter from Dragon vol. 310 gets it at 1st level—alongside another bonus feat, which could allow for taking a feat a level early, too (though the pugilist feat list is fairly limited).
Compared to the marshal, this approach locks in your racial choice in order to save a feat: compared to a human marshal, you basically gain the benefits of the frostblood orc or half-orc’s other features—which leave a lot to be desired, thanks to the vulnerability to fire. However, the opportunity to use something other than marshal—which is a pretty terrible class—can easily make this a win for the right character.
Half-elf or human paragon
The variant racial paragon classes from Unearthed Arcana for half-elves and humans both include a bonus feat that can be any the paragon qualifies for. The half-elf gets it at 1st level, while the human gets it at 2nd.
Superficially, this approach costs much less than the frostblood (half-)orc, being just a race and one or two levels. The half-elf version also saves a feat compared to dipping marshal, since you don’t need to take Skill Focus (Diplomacy). But the half-elf race is notoriously poor, so much so that a human marshal or, in the right build, a frostblood (half-)orc, could easily be better. Meanwhile, the human race is one of the best in the game, but human paragon 1st is an extremely poor level, with almost zero going for it—dipping fighter to make up for the feat spent on Skill Focus (Diplomacy) is the better use of your resources for most characters.