I'm calling . .. .. .. .. .. .. .. . on that. I'll tell you why when I debunk your second paragraph.
Exactly. So, listen: no one wants to remove all randomness. I never said that, my mod goes nowhere near even trying that, and as you point out yourself, the very notion doesn't even make sense.
My mod removes unpredictability from combat results. Everything else is as in the normal game (as far as luck is concerned). Civ4 (and FFH even more so) is such an impossibly complex game that there's always a whole lot of randomness involved. Maps, as you pointed out, are random each time. But even if you played on the exact same map with the exact same starting positions, no two games would be alike. Every little decision you take differently opens up a whole new decision tree, meaning that no two games will even be remotely similar.
And if you take a moment to consider that, you'll see how beautifully it devalues your first argument. Combat randomness adds nearly zero replayability because in the great picture, the little variations that are added by losing a combat you should have won etc are negligible (as far as number of possible game situations goes). That is not to say they do not matter for the game you're in--they matter greatly. But what I'm saying is that they do NOT restrict the number of game situations you can experience and as such add no replayability.
I was not talking about your mod but general theory

In fact I like your combat idea VERY MUCH. I myself get puzzled after ridiculous combat results. My friends and I often talked about how it sucks and that best solution would be that battles over 90% odds should never be lost, even if lost attacker should win but have 1 hp left. So battles over 90% would be what they are basically in my mind - sure victories with only one question: How much damage will attacker suffer?
About your mod : I'll try it when I'll have more time (And hopefully you will fix first strikes somehow)
What I don't like is messing with mobility. Horses should start with more movement than infantry. Plus without railroads stuff will just move too slowly.
Could you implement (since I see you understand programming) battle system from Afterworld, where it takes few combats to kill unit (At least for heroes and T$ units?)