Only two playthroughs are required, but one of them has to be of the Advance Campaign.
COs only become available in Battle Maps after finishing a campaign in which you completed their unlock requirements, as follows:
- Grit: Choose Max for Mission 4, "Max Strikes!"
- Eagle: Complete "Captain Drake", "Naval Clash", "Wings of Victory", and "Battle Mystery" with Sami, all on the same playthrough. An Eagle campaign will also force you to complete the bonus chapter, "Rivals!", after "The Final Battle".
- Drake: Complete "Captain Drake", "Naval Clash", "Wings of Victory", and "Battle Mystery" with Andy, all on the same playthrough.
- Kanbei: Complete the campaign -- Kanbei has no special requirements.
- Sonja: Complete Sonja's missions during the campaign. To access them, you must complete Missions 9, 10 and 11 within certain turn limits:
- "Kanbei Arrives!" in 8 days
- "Mighty Kanbei!" in 10 days
- "Kanbei's Error?" in 12 days
- Sturm: Purchase all of the previous COs available in Battle Maps.
- Nell: Complete the Advance Campaign.
So, if you play through the campaign normally and get either Drake or Eagle, then do an Advance Campaign with the other's requirements, you will unlock all the COs in a minimum of missions.
Please note I haven't given any consideration to the relative difficulty of this route. The normal campaign isn't too bad, but for the Advance Campaign I might suggest a turn-by-turn walkthrough such as this.