Another (although limited) remedy for the AI naval problem was found in MedMod. WesW identified the sea below the Adriatic, the Marmara sea and a few others as main the obstacles to an at least partially successful AI naval deployment. Their removal significantly increased the chances of the AI establishing ship chains. In addition, the strait of Gibraltar was changed into a deep sea square, thus cutting off travel & trade between the Med and the North sea....at least during early.

although some of caravel's points are valid, I'd opt against a purely land-based orientation. actually in my games the AI doesn't fare too badly naval-wise (could be better, though), it conducts quite a number of naval invasions and isn't easily outmatched by me. of course one has to abstain from spamming the seas with loads of ships as this would ruin the challenge....and also be highly unrealistic.

the factions reappearing on isolated islands are really a problem, though, and should be addressed somehow. all the more since islands are more prone to reappearances because they're more easily isolated from the king due to the not-always-that-perfect AI naval movements.... AFAIK there is no possbility to mod the reappearances in order to either provide a couple of ships when a faction respawns on an island or prevent reappearances from happening on islands altogether, but I'm not the greatest among modders so if anyone knows better....