As nzcamel pointed out, representative confederate governments were nothing new in pre-Columbian North America; the League of Five Nations predated Columbus by several centuries. It's true that their regional prominence rose considerably after the Dutch armed them with guns and the British eliminated a few of their rivals, but their own experience with politicking is what allowed them to survive as a major regional power even in the midst of European colonies by playing the major powers off each other.
Representative government is common in small societies and tribes; the Anglophone parliamentary tradition has its ultimate roots in Germanic tribal councils of the sort that persist today in Iceland's Thing, and local councils are a common form of local-scale government even in monarchic societies. Societies tend not to develop autocratic centralised authority until they reach a certain level of complexity and urbanisation, and need a structured central government to oversee resource distribution.
That's not the same as what nzcamel describes as "constitutional government" and - at least as Britannica Online has it - the Iroquois Confederacy was a specific response to external pressures (principally European incursion): "Cemented mainly by their desire to stand together against invasion, the tribes united in a common council composed of clan and village chiefs; each tribe had one vote, and unanimity was required for decisions. The joint jurisdiction of 50 peace chiefs, known as sachems, embraced all civil affairs at the intertribal level."
The Iroquois system was more formalised than anything preceding European contact, and as the same source has it "more consciously defined". That's getting to a point where it can be described as something close to 'constitutional', but it's stretching the point to suggest it's likely to have had specific influence on the development of American government traditions which explicitly rejected representative parliamentary government in favour of a classically-derived republic.
They were indeed important brokers between European powers, but that's a role they owe largely to the conflict between those powers which prevented any one becoming dominant for two centuries and the fact that none of the European powers had purging the natives among their objectives; it wasn't as remarkable in their eyes as it is to ours in retrospect that significant native powers would remain on the continent in territory not then claimed by any of the European competitors. The large-scale displacement and elimination of native tribes came about only after the formation of the United States (stories about European colonists deliberately inflicting smallpox on the locals are anachronistic as they conflate different timescales and events: this was documented, mostly at localised scales, during mid- and late-18th Century wars onwards, both wars of eradication prosecuted by the US and as attempts in the French and Indian wars by European powers to kill or debilitate native auxiliaries. It isn't supported as far as 16th Century colonisation is concerned, nor is it very credible as the European settlers themselves were not immune to the disease at that point, and they were heavily reliant on local knowledge for their early survival).
None of this is to suggest they didn't have an important formative role, but that role is likely to have been overstated and insofar as that's their major claim to relevance it's not clearly enough to warrant a place in Civ. If the only major role in international history the Dutch had was their part in the founding of America, would they be considered worthy of including in Civ?
Leaders from the Dark Ages (5th to 10th century A.D.) are fairly rare for Civ though. I can only remember a handful from the top of my head for this entire franchise (Justinian & Theodora, Ragnar, Abu Bakr, am I missing someone? Wu Zetian?). It would be nice to add a few more names to that list.
Attila and Harald Bluetooth, at least, more or less bracketing that entire period. Given Dark Ages are a part of this expansion I think they'll have at least one nod to *The* Dark Ages, but I'm not sure what it would be. The Celts led by Brian Boru are a possibility; it's at the very tail end of the period, but the Dark Ages ended at different times in different territories.
I found CdM sort of threatening in an insidious sort of way. Gilgamesh just looks ridiculous.
I'm probably getting it largely from Gilgamesh's voice - one of the few leaders who actually sounds as though he's speaking to you rather than reading from a script (I can get used to the animation in Civ VI and quite like it in some respects even if I'll always prefer the Civ V style, but I'll never get on board with Civ VI's voice acting).
Catherine's mannerisms and her head and neck apparently taken from Cluedo are too absurd for me to find her in any way threatening, insidious or not.
Philip is such a disappointment; not only does he look nothing like the real Philip, but the real Philip was supposed to be cerebral, melancholy, and reserved.
He's still a sort of entertaining figure, though, if you pretend he's not Philip II of Spain; maybe Antonio Banderas playing Don Juan impersonating Philip II of Spain or something.
Gilgy is ridiculous...but that's kinda the point I think.
)
It was suggested potatoes as the new resource & I'm especially on board for tubers because of one of my favorite articles.. 
