... another unlikely pairing, that of P&P's Darcy and Bingley. One's intellectual abilities and the other's social abilities complemented each other and made them fast friends, even though there seemed to be no common ground for the two. This strikes me as a very similar pairing.

Regarding their meeting: absence of evidence is not evidence of absence. Again from P&P, younger sons of titled families were sometimes (often?) sent off to the military to make their way in life (and to get relief from the danger of family jealousies?). Think of Col. Fitzwilliam. Middleton could have been a highly valued enlisted subordinate or a fellow officer, called "sir" rather than "colonel" for a family title or a knighthood granted for noteworthy service.

Someone suggested in the P&P group read that Darcy might have been a student mentor or tutor of Bingley, which introduced them to one another and made them fast friends. Why not a similar convergence for Brandon and Middleton?