In Civilization 4, the best pre-medieval era unit is undisputed the Preatorian, I can take walled cities with Preats without needing cats and have found them to be an invincible unit from the invention of Iron Working (which can be researched in the first 17 turns if you beeline it, less if you have a good starting spot) until machinery which is more then 100 turns later (on average).
I have beaten Diety with Rome, but can't touch immortal with any other civ.