The key to combat in Civ3 is to strike in numbers. E.g. turn up with at least 4 times as many Horsemen as you expect resistors.
Aztecs are highly effective early on though due to their Jaguar Warriors.
I usually play Aztecs and just finished a game on Regent. I had wiped all of my continent, destroyed the Iroqouis and relegated the Americans and French to one city each on seperate islands. Pretty much all with Jaguar Warriors and a few Horsemen later on. All I was really after was a Great Leader so I could build a damn Forbidden Palace!
How many battles do you need to fight with elites? Normally, it isn't that hard...
I got bored by about 100AD as I had about 50 cities, about 40 of which were useless due to corruption, Forbidden Palace was going to take 200+ turns to build where I wanted it and without a Great Leader it was just dull and boring
So, I decided to spice the game up a bit by giving away all my cities to the remaining four AI players - turned my empire into a multi-coloured checkerboard hehehe and played until around 1850AD as OCC when the Germans finally crushed me with Cavalry...
Civ3 is such a silly game
I wouldn't bother playing with Barbarians if I were you, unless you really want to. There's no score penalty AFAIK. If you want to make things harder for yourself, play at Monarch or something.