Speaking just about regions that we know enough about historically (and which donāt need egregious creative license to work), I think Africa and the (non-North) Americas are the ideal next choices to focus on. Europeās plenty saturated, albeit ripe for some notable inclusions later on (ex. Slavs split into a few civs across Balkans/Ruthenia, Swiss + Frisians for the Low Countries, maybe Venetians with an emphasis on their larger Mediterranean holdings and syncretism). And while thereās a bunch of Asian civs that deserve attention, weāve recently had Last Khans and now Mountain Royals to flesh out Eurasia, so Iād personally go with (South) East Asia first. Who knows if thereās ever going to be a sure fire way to add Tibet/Tubo, even if disguised as the Qiang. I get where the Polynesia advocates are coming from, but the Tongan Empire was far more about trade and chieftain prestige than conquest and any kind of bureaucracy, let alone having more technological isolation than even the Americasātheyāre a long shot at best. Brunei and the Visayans could help fill that gap, perhaps.
WRT whether they could add Songhai without it becoming redundant, the emphasis there should go to the empireās coastal holdings, as well as adjacent powers like the Jolof. They engaged in slave trading far more than old Mali, and Sonni Aliās rampage through the western Sahel (followed by Askia the Great trying to manage it) gave them a distinct identity. Kanem-Bornu can distinguish itself as the mediating power between Songhai and the Hausa states, with more of a cavalry focus due to Berber/Ayyubid proximity. A new West Africa DLC ideally features the Songhai and Kanurians as new civs, plus a new and improved Berber campaign (with Tariqās campaign becoming an official mod).
Iād be keen to see how far FE could differentiate the Adal/Ajuran Somalians from the Swahili sultanates, given they both derived much of their power from coastal trade and naval control, but both would work great as civs. (Would suck for Ethiopia to have another campaign where their empireās basically toppled, even if Gelawdewos saved his country in the end.) Christian Nubia has everything it needs for a great campaign where you contend with Ayyubid invaders (better yet, the initial Rashidun invasion), plus the chance to swap archer bonuses with Ethiopia for historic accuracy. You could even add in a valid Polynesian civ via the Malagasy (Merina Kingdom), which we know quite a bit about and whoād offer more design space than normal. Letās not forget the Bantu kingdoms; Zimbabwe (Mutapa & related Shona) and Kongo would be trickier to design since they mainly warred with early Portuguese colonials, but they fit into the end of the timeline reasonably well. For the initial DLC, Iād choose Nubians (Makuria-Nobatia), Somalians (Adal), and Swahili (Kilwa et al.), plus a reworked Ethiopian campaign centering on the rise/peak of the Solomon Dynasty.
The Americas are tricky, as always. If FE were to split DLCs by region here, the clear Mesoamerica choices would be the Zapotecs and Purepecha, both non-Mexica peoples whose states resisted Aztec/Nahua hegemony and which reacted differently to Spanish conquest. The former would have a bit of Andean flavor, mixing boni/uniques from the Aztecs and Mayans. Given their metallurgic prowess and well-organized defenses bordering the Triple Alliance, the Purepecha makes most sense as the main defensive civ for the region. Top this off with a proper Mayan campaign and weāve got a strong pack. South America mainly needs the Chimu and Mapuche, both to enliven the Inca campaign and to cover alternate angles of Andean conquest. I love the contrast between a centralized, naval + infantry Peruvian rival to the Inca (emphasis on offense) and a looser, archery-focused guerilla civ which can get late-game access to some kind of cavalry/foreign tech. Sadly thereās no strong civ choice east of the Andes, and I honestly donāt think the Muisca experienced enough complex warfare or resistance to conquest for them to really work.
Honorable mentions to the perennial North American choices, too. I think both the Mississippi and Haudenosaunee can effectively share an architecture set and have strong campaign premises (Tuscaloosa/Quigualtam vs. De Soto + Forming the Great League of Peace and repelling the French). Theyād be pushing right towards the edges of the timeline, just like the Mapuche, but shouldnāt necessarily intrude on AoE 3ās history/design territory if handled right. Still, FE should practice due diligence and consult indigenous experts on how best to represent these cultures while providing a fun, meaningful experience to players. I believe any DLC tackling North America would come towards the end of the development pipeline, if ever.