Other than Bahamut and Cid, I haven't really had to do more than 30 matches against anyone to get their card, although I haven't really taken on many of the high-level people. I got Minfilia before Y'shtola, a second Godbert before I realized I already had one, and I'm always surprised to find duplicate cards in my inventory after running a dungeon. Even for Bahamut, I was just showing off the Triple Triad games to my friend to try and lure him back to the game, and the very next match after he walked away I got Bahamut. Mostly, I just play matches while queued and almost always get the cards within one or two queues.

Now gold packs. Those are a pain. Always Momodi and Baderon. So many Momodi and Baderon. Why u no good to me gold packs!? T^T