Zanzibar: A perfectly placed city for a trade hegemony, yet it truly was dealt an awful hand through history. Give it more time and trade influence across to Indian bringing in migrants, it could then be a very large city by the modern area straddling the islands and onto the coastline.
Palmyra: In a no Islam scenario or one where the Umayyads choose it as their capital instead of Dimshaq, becomes the capital and most populous city in Syria, especially with canals and a continued economic boom in Baghdad or Cteshipon.
Baghdad: With certain criteria, going back to the Abbasid period, could be the largest city in the Arab world instead of Qahirah. Ways for this to occur, briefly:
-No moving of the capital to Samarra in the late Abbasid era.
-No Zanj, Khawarij, etc.... rebellions to destroy its vital countryside. This would entail the slowing of the slave trade to the Batihah Sawad, which contributed to the mass poverty leading to Baghdad's economic failure in the 1000s AD.
-No Mihna, or inquisition. This was the fire that started the end of the Abbasid period and of the caliphate.
-Keep the Abbasid court religiously neutral but publically Sunni. Simply put, keep the vicious and greedy Mu'Tazila from the reigns of power in Baghdad, which caused the fall of the Abbasid caliphate (the Abbasid was essentially a Mu'Tazilite state as opposed to a Sunni one).
All these points butterfly the Mongol siege, as we assume the Caliph is not idiotic enough to assist the Mongols in taking Alamut from the Hashashin and putting forward no resistance at the walls of Baghdad or more importantly in the south in the defense of Basra.
Vijaynagara: A state with huge potential and with a city likewise. It could've become a trade juggernaut, but was snuffed in the cradle by the Bahamani, who also could fit this criteria from its fort at Bidar.
New Orleans: Speaks for itself, once the largest and most diverse city in the southern US.
Novgorod: The typical.
Etc... I could go all day.