Combat is a matter of probability but this combat formula, in comparison to that of CivII, allows for computer victories which lean towards outrageous, most unbearably so when the human player commands an obvious numerical advantage. Unit promotion in CivII meant that unit received attack and defense bonuses rather than HP, and most importantly, units could be damaged in much smaller increments. So the greater the number of attacks between any two units meant that the outcome would more accurately manifest the higher rating of either unit. Or, if you had a cube which you rolled 6 times, you may get 3,1,5,6,5,4; if it were to be rolled 100 times, each number would appear in a closer relationship to the 1:6 ratio, and if 1000 times then even more so. Thus streaks of luck (good and bad) in combat will be proportionate to the length of the conflict, or the HP of the units, as much as the attack/defense unfortunately.
Of course other factors influence a victory in both Civ games: occupied terrain (which offers a much smaller advantage than CivII), improvements, promotion and such. CivIII brought other factors - trans-river combat, town-metropolis defense bonuses, fast unit withdrawal, defensive artillery, etc. In addition to the lack of quick and/or high-attack ancient units (elephants, legions, catapults), this makes an offensive war much more difficult before the discovery of chivalry, unless aided by a unique unit like the Immortal. No more riding the enemy's roads and railroads, attacking multiple times in a turn, splitting them with a capital assault; so 3 turn elimination of an empire is almost impossible if both are well matched. The Infantry unit also contributes to national stalemates as a WWI recreation, until, as in 1939, tanks are deployed.
In general the death or survival of a unit is subject to chance more often than in CivII, which reduces the commander's ability to decide the course of a war. While this is realistic in certain cases, it shall never contribute to a more satisfying game, because too much chance is a gag and not a garnish.
Does the level of difficulty affect combat outcomes? I think the AI merely steps up its tactics a bit and unhappiness is increased, but please notify if otherwise.