Hmmm... So we're pretty much down to RFC or maaaaybe Earth 1000 A.D. It's a tough decision. E1000 would be more "traditional." To avoid retreading familiar ground and repeating old leaders, I would be pretty much limited to Charlemagne or Justinian. I could also justify Ragnar, Wang Kon, Suryavarman, Elizabeth, Peter, or Louis there.
Rhye's-wise, I'm kind of at a loss. I've already done China and India. Maybe Greece or Egypt for an "early" civ with the option to jump ship on a later turn? Would a switch be in keeping with the spirit of KotW? I'm pretty intimidated by the mod, let me tell you.