Lincoln is a curious choice, considering the fascination with him currently in film and books. He and Surak don't fit the bill, really, considering the contest. I'm not sure who to replace them with, though. Maybe somebody like General Patton?
Napoleon should have been in there somewhere - maybe with the villains as a sort of a tactician.
But the Excalbians weren't just testing fighting skills, though that was what their method boiled down to. Their stated goal was to test the relative strengths of the philosophies of good and evil, based on archetypes taken from Kirk and Spock's minds. And Kirk and Spock defined Lincoln and Surak as their archetypes of goodness, because they value freedom and peace.
The problem is that the Excalbians chose the test poorly. It isn't brute force that defines the superiority of good over evil, it's all the things that good accomplishes in other aspects of life -- the way it provides alternatives to violence, heals its victims, and so forth. Good is that which builds and heals, while evil is that which destroys for the sake of destruction. So reducing it to just "Who wins in a fight" was missing the whole point. (Pet theory: The Excalbians were actually Internet fanboys acting out a "Could Superman beat the Hulk" kind of debate.)
The other problem is with the choice of villains. The handling of Genghis Khan was deeply racist. For one thing, it's only Westerners who see him as a monster; he's a national hero in Mongolia, and the empire he built brought peace, prosperity, and free cultural exchange to much of Central Asia for generations after the violence of the conquests had ended. Basically the East sees Genghis the same way the West has historically seen Alexander the Great -- another conqueror who was extremely ruthless and brutal in building his empire but relatively benevolent toward those who accepted his rule. The main difference, of course, being that Genghis was far more successful than Alexander, building a much bigger and more enduring empire. So calling Genghis simply "evil" is an oversimplification owing more to racism than historical truth. If he was evil, then so was Alexander.
Which is the other problem: Genghis was no mere mute henchman. He would've been the most brilliant and accomplished military strategist and leader in the group. He, not Col. Green, should've been the leader. After all, Green was just some petty bigot who wanted to exterminate the impure -- not the sort who's good at working well with others who aren't like him. Genghis was the unifier of his people, as much by charisma as by force, and he welcomed religious and cultural diversity in his empire, since nomadic peoples tend to interact with a lot of different cultures and have a flexible view of the universe. So Genghis should've easily taken charge of the whole group and led them far more effectively than Green. (I'm discounting Kahless because the modern conception of the character didn't exist when the episode was written, whereas Genghis was a real historical figure.) But Green was the white guy, so he was put in charge and given all the lines.
I wonder why they didn't just make Hitler one of the bad guys. Pretty much all Americans (except the Nazi sympathizers) had seen him as the ultimate embodiment of evil ever since WWII. And there were plenty of movies and shows in the '50s and '60s that portrayed Hitler as a character. But instead they decided to go for Col. Green as a sort of Hitler surrogate, only much less menacing.
