Having Cleopatra leading either Macedonia or Greece is making as much sense as Abraham Lincoln leading England. After all, both of them have ancestry from a foreign region! From Ptolemy I Soter to Cleopatra VII, there is a wider gap than the American War of Independance and today.
We should focus a lot less about the ancestry, and focus a lot more about what civilization, state, nation... those leaders actually lead.
I understand the appeal of having Catherine de Medici leading Italy. The main golden age of Italy was during the Renaissance era at a time the peninsula wasn't united. It is tempting to have an "Italy" where leaders are from the main City-States like Venice, Genoa, Bologna, Florence, Milan, Vatican city... as a way to circumvent an united Italy under Mussolini (I don't think we are going to have a fascist dictator in the game). Here, Catherine de Medici would "fit" the Florence leader, but she wasn't in charge. It was Cosimo.
For Saladin, it is complicated. Because the concept of Arabia is complicated. Where Maghrebi people often saw themselves Arabian, yet not Arabian citizen. Saladin himself was in charge of today Egypt, Syria and the southern part of the Arabian peninsula, si it could "fit" the Egyptian leader. Yet, people are already complaining that Cleopatra is leading Egypt, because she is a Queen and not Pharaoh (but took the Pantheon and called herself Isis: she did try to emulate something). I don't think Saladin would be better accepted knowing he completely broke away from the ancient Egypt. So we have here "Arabia" as "Muslim middle east, including Egypt" more than anything. This is the Egyptian curse: that is why you don't have Vercingetorix or Charlemagne as French leader, and if they are coming, they would be under a Gaul and Frank Kingdom instead of France. I wonder if they are going to use dynasty name like Ayyubid. After all, they currently use Ottoman (dynasty) instead of Turkey.