Well if we go middle east there are still some holes in the map, in the bronze age we can have the kingdom of the Nabataeans, who built the region and were also the predecessors to Arabs, imagine the Greek kingdom of Bactria, kingdom of Israel, and we might finally see something other than an independent city Jerusalem blocking way.
Also if we start adding crusader era civs Armenia is a candidate, and probably the Muslim powers should be more diverse, with constantly changing names to represent all the different caliphates.
Thinking about Oman too, a trade civ, maybe with like India and Africa contact and resource uhv. Maybe a UHV like become friendly with India or get X timber and Indian resources from them by trade.
With the new map maybe it's all possible