Last night I was testing on Civ 3 against a size 11 city. They had numerous infantry units, varying from conscripts to regulars. I had about 20-24 veteran-elite Cavalry units. I was attacking from Grassland and there was NO way I could get close to killing them. (The max I was able to take out was one regular Infantry.) But once I got onto a hill, I took the city with no losses. So maybe the Cavalry unit is not the problem, but the AI's inability to secure hilltops and other strategic terrain squares?
Also, some observations about combat with Cavalry vs Infantry. It seems like that the battle is very dependant on who draws the first blood in the fight. For example, a conscript infantry can take out a veteran cavalry (no retreat) on grassland if it dealt damage first. What's more surprising is that more often than not, the infantry will -not- take any damage from combat. However, if the Cavalry unit hits first, then it would most likely kill the Infantry unit. Surprising, no?