I've had simlar experiences against the Carthaginians. While cavalry are indeed powerful, they are most certainly not unstoppable, and in my experience I don't find them TOO powerful. More powerful than they were in MTW? Absolutely. But then, I always thought they were slightly underpowered in Medieval.

Of course, I haven't faced off against the Macedonians or Egyptians yet, so perhaps I'll change my tune when I have to fight some of the more elite cavalry in the game.