I think it's a bit to late in development for major mechanical reworks. We finally got better performance and AI in 1.34. Adding more mechanics to 10 year old code is risky.
I believe well made Flavour Packs are the way to go.
Caucasus region (Armenia, Georgia, Circassia, Chechenia, Azerbaijan) would be a good idea for Flavour Pack. Their missions are barebones and they lack achievements. It would nicely fit between already reworked Persian and "Horde" regions in the north. As a bonus, you could add something to the Cossacks and Crimeans since they were unique powers in the Black Sea regions that are not that well represented in the game sadly.
Since we got playable Aborigines, which proves that for EU4 Gameplay>Historical accuracy, maybe we could get more playable Siberian tags, like Yakuts or Chukchi. Yes, we have few tags in Kamchatkan region, but they lack flavour. Few more tags and rework for already existing ones wouldn't hurt.
Brazil/Patagonia is another good idea. Natives there never got any reworks.
People talk about Middle East, but which countries do you mean exactly? Maghreb region was nicely reworked in Golden Century, Mamluks in Craddle of Civilization, Persians and Timurids quite recently too.
Only Lebanon, Palestine and Arabia are lacking a bit in the Middle East. Maybe it could actually nicely fit for "Crusader" themed DLC.