It is difficult as they have as I understand it a monoploy on trade through the straights with some agreed exceptions. Whiel Crusader fleets can ignore that you will have more problems
Good idea. Venice could be an interesting side adventure
That is the same as option 1 actually. I myself suggest that he heads for Barcelona and set sail from there, to Sicily then to Greece. That is the actual trade route used back then.
Any of the land then sea routes are viable and all have potentially interesting complications
I prefer not to abuse Leap of Homecoming too much . All of the magical ones essentially come down to bribery
House Mercere are know to have Hermes portals between the Mercere houses of tribunals and their Domnus magnus . So two journeys would get you too Greece. They are going to charge at least 4 pawns of Vis per head for this probably more.
It is beleived that one of the mages of Vindolanda has a Hermetic portal to Constantinople as she certainly seems to run a good business selling eastern goods and that is thought to be her source. You have no idea what her price would be. She is the one who you gave back her boat after the pirates took it.
Someone must have a flying carpet you could rent.
Shadows of the past has numerous items for turning people into animals , some of them may be good for travel.
You could try and find a route through Arcadia or the Magic realm (Good luck with that)