I agree with ianw1610 that we should avoid trading with Mehmed. Unless it is absolutely required to prevent Isabella from being wiped out, we do not want to risk up to -4 with Saladin (and Isabella). We are going to need Saladin's votes, whether our eventual rival is Mehmed or Justinian, and -4 would be a very significant setback for us.
With no state religion, Theocracy does not give us any XP bonus. We are going to have to plan for an eventual change of religious civic, as we must have a state religion and have it present in all our cities at the end of the game. This will include any barb cities we capture at Devil's Gate and beyond. We should not leave this to the very end, as we will need to shift back to Theocracy for diplo at the end and may need some turns to re-establish the full bonus with the relevant AIs.
About barb cities...do we want to capture them? Or raze them? They will increase costs, especially if there are several cities to cause colonial expenses. But they also represent additional votes, plus production sites close to the front. Also healing, upgrades, and airship bases. I suppose we could always spin off a colony, although I have never liked doing that since the new AI tends to trade away all of your (formerly) monopoly techs.
Very good news that Justinian has shifted out of WHEOOHRN mode.

Keeping all of the western continent AIs happy with us will help greatly with tech trades and keeping relations penalty free for eventual UN voting.
I still think we should find time for a caravel or two for exploration. We may not need them, but I would prefer not to bet on that. And if we build them soon, they can explore over time and we do not have to worry about needing a sudden exploration rush later in case Devil's Gate is a red herring.
What is our position for obtaining the other required resources? Ivory was available, but we also need dye and silk. And it sounded like Mehmed was the only possible source of silk.