I think there are two cities that are going to be the most difficult to get to in a reasonable amount of time, Medina and Susa.
If we keep Damascus, then getting to Medina would be less of a problem, and I would argue we should keep it if Medina is heavily defended The screenie below in the spoiler shows an idea of what we might try to do.
I think that all our troops in Galleons currently around Ecbatana should go to the Persepolis area unless it is revealed that we need far less then that. Additionally, the Galleon near London should head for the area south of Baghdad in search for the missing Arabian city.
I like taking Haithabu (rather than landing north of it) and using the road inland from that city to find the other Arab city -- where else would the road lead.
In the meantime, the Galleons used to transport the units to Persepolis can begin to form a chain. Thunder Rider to Leif's to the next one, etc. leading to Tarsus. We run this chain twice then all Galleons head to our home shore to begin transporting units to Vikingland except for MP's FL coming down from Damascus, checking on Medina, and ending up near Gordium. Whichever Galleon moves to the west of Tarsus transports units to Gordium and then helps ship them to Medina. From there, whatever is available moves units from our coast to Haithabu, Birka, Nidaros and Uppsala to finish.
Maybe, and I definitely agree that we need many of the galleons to head home for the end game, but I'd like freedom to play this as it goes.
I calculated that, with favorable odds, we should be at Susa in 12 turns or so, providing we can use the roads, and that they exist, from Pasargadae north. We may not make Medina in 12, it will be tough as we'll really have to push it. We can look closer at that once we see what is in Medina?
I like SCT's suggestion to send Bagdad units that way.
EDIT - I agree with going for HBR once the chop is in.
SCT and Gator are both against this, so I'm going to hold off.
Do we have an axe that we can put just out of range from the chariots for a turn to try to lure them out of the city? Or can we bounce AI units by leaving a city empty (as in Civ III)?
I think they will come out to counterattack Mecca without provocation.
EDIT2 - I also agree that it would be nice to pop-rush a couple more Galleons.