We know that the Aegean islands formed a maritime theme later on where most of the sailors were recruited from and the Greeks, in general, had been a primary source of sailors for the Roman Empire since the very beginning. I see no reason why this would change.Guys, there's something that's been puzzling me for a while.
As you may have been aware, Romans in the Roman army have been on the numerical decline since the time of Augustus, but the entire process accelerated in the Constantinian era, leading to the barbarian Roman army of the 5th-7th centuries we are all familiar with. I have read much on the subject so this isn't the part that puzzles me.
What is puzzling me is this: who manned the Roman navy, and why on earth do they keep fighting even when the army was broken, imperial finances were broken and imperial morale could only afford hiding behind walls? Were they barbarians of a different mental caliber compared to their cousins in the army?
Or were they Roman?
If we can't answer this question, we would be going nowhere on the subject of the OP - which is, how could New Rome fall in 718? It isn't something that could be butterflied away by saying "no Greek Fire", since the Roman Navy itself (as much as Battle of the Masts is brought up, it was not a decapitating blow to the Roman Navy), Coptic sailors' spiritual unity with the Christian Romans, sickness, supply troubles and of course good old fashioned infighting all factored in the OTL failure of the 718 campaign. Understanding the demographics of one of the most important participating forces is crucial to understanding where to place the POD.
In the context of this discussion, I am not sure if it's actually possible to completely destroy all potential for a navy, in what was basically a thalassocratic empire. Even Andronikos III freaking Palaiologos was able to build up a navy of 70 ships. The best one could hope for is to have the imperial fleet destroyed, with regional ones too far or too weak to make a difference.