When you click on a leader you've met, you can see your access level to information about their civ. By default, you won't have much access, but your level of access increases if you establish an embassy, establish trade routes, have a spy perform the Listening Post action in their city... etc. I believe that if you click on the level of access (or nearby it), you'll be able to see a list of actions you can take to increase access and what that new access will get you. France gets bonuses to level of access, so it's a natural choice to try to get the achievement quickly. Access is also easier to obtain in later eras thanks in part to spies, so a late era start would be faster.