And then there are Kirk and Spock. Why are they on the "good" side?
Because the Excalbians chiefly want to learn why Kirk considers himself "good"?
I mean, that's where they got the concept in the first place. Kirk has this image of himself, and the talking rocks want to deconstruct this intriguing concept by asking Kirk to provide examples of "not good", as well as further
examples of "good". For all we know, they also get the idea of "fair play" from Kirk's mind, and thus decide on equally sized teams.
As pointed out, Khan was Kirk's hero. "Space Seed" need not have changed that much, and perhaps even Spock learned to appreciate the man after this episode. Khan basically embodies Kirk's own virtues of strength, manliness and fair play, merely taking them to the next level.
The gold standards of evil change with time. Quite possibly, Green out-did Hitler by a wide margin... OTOH, it's difficult to out-do Genghis since, as pointed out, his conquests and atrocities compete very well with those of later leaders in both relative terms (taking into account e.g. changes in Earth population, morals and speed of transportation) and absolute ones. To accompany Genghis, one needs a specialist in some narrower field of evil, hence Green and the rest.
Heck, it's ethnocentric to classify Genghis as "evil" in the first place.
Not at all. A slaughterer is a slaughterer.
What would be ethnocentric would be to label Alexander the Great as "not evil", but nobody is doing that in the episode.
People killed in the name of Lincoln and Surak, too, and even specifically under orders from Lincoln although possibly not from Surak. But since Kirk is a professional killer himself, his definition of good cannot include "does not kill", in which case it's all the more fitting that both the "good" and "evil" side feature killers. Thanks to this, things like numbers and motivations and excuses come to play, and Genghis Khan clearly loses to the other leaders in that contest.