There is a good core of totally corrupt cities to gift to Arabia. We can use those same cities for England/Zulu later.
Thebes, Alexandria, Seville, Barcelona, Madrid.
They are size 3-7 and in range of our core so we can get 5 horses there, who can take them all back in one turn without breaking rep, or risk of auto raize. There are three horses right there, use the ones from New York, and Washington and those 5 should be used to retake them.
Most important thing is to get Fez in a peace deal.
Turn of events should be
Gift 5 cities to Arabia
Declare war (next turn we have troops around those cities, move them out)
Move the horses into place, but you'll need to wait for peace
When they will negotiate, only then, take Muscat, use 3-4 Knights.
On the turn that Muscat falls, go to dip, see if they will give us Fez for peace.
The palace should be in the 5 now.
Take the one with the palace, go to dip, see if they will give us Fez for peace
Repeat for all 5 until the palace has jumped back to Aden. Then stop if we still don't have Fez we are in trouble.
If Fez is size 2 then stop before destroying all 5 on the other continent.