To my surprise, I beat the Saladin mission "J***d!" a few hours ago. I was seriously contemplating giving up on it and moving on, even after skimming a bunch of walkthroughs. Sure, it may not have been as dubiously hard as "A Perfect Martyr", but on Hard, the Yellow AI creates a killer navy that I doubt you can defeat. In all the AOE2 campaigns I've played thus far, I've never had to deal with Heavy Demolition Ships. Suddenly, out of nowhere, here's an AI that attacks you before the 30 minute mark with 4-6 Heavy Demo Ships, 6-9 Galleons, 5-7 Fire Ships, and 2-3 Elite Cannon Galleons. If that's not enough, you're probably still in the Castle Age because you'll spend the first 20 minutes defending against two land-based attacks. And, of course, the Yellow AI also sends the occasional Transport Ship filled with Cataphracts, Onagers, and Bombard Cannons. Wheeee!
In the end, I went with a tip I read somewhere online and abandoned my starting base that's dangerously located along the coast. When the Yellow navy came knocking, I evacuated my villagers and created a new Town Center farther inland. As I was building my new base, the enemy Cannon Galleons managed to destroy nearly every building and wall section save for a few of the innermost tiles. Not having to worry about that damned fleet was a huge relief, so I managed to rebuild and eliminate Yellow when I had Elite Cannon Galleons of my own.
The next and final Saladin mission is "The Lion and the Demon", and by all accounts, it'll ruin me. Geez.