I think Lincoln is probably the best choice, but does it have to be a President? Why not Martin Luther King, Jr., for example?
Which leads to their own inconsistencies, now that I think of it (ah, the dangers of speaking from one's own buttocks...). For instance, Joan of Arc. Certainly historically significant, but she was never the head of state of France. They could have picked another great French woman for the female ruler. Catherine de Medici? She at least held real political power.
Of course, this leads to problems in the U.S. as well. Will they still make Eleanor Roosevelt the female leader? Who is the Germans' female (Austria's Marie Theresa perhaps???)? Ohhh, the questions I have!
Comment