My Legionaries do okay against them, mostly I think due to the numerical advantage. They also have solid armor (like 36 or something base). I'm also a newb and play on Normal/Normal....something I will likely change in the future.
The game has gotten kind of easy, as I was able to get Marius quite early. I'm not sure if maybe I'm just better, or the legionaries are just powerful (for the most part I use Principes pre-Marius, which are similar enough to the Legionaries).
Legionaries make up the overwhelming bulk of my military (Gallic warbands for garrisons, as they have cheap support costs and a large number). They seem to be able to go toe-to-toe with almost anyone, and as long as they aren't surrounded and flanked, tend to win most of the time.
I have noticed that the odd time I have picked up mercenaries (simply because I had concerns about numbers I was about to face), they absolutely do not last as long as the Legionaries. I bought some of the armorless, 120 stack German mercenaries because they were cheap and had large numbers, and some Javelineers did quite a number on it. As a counterpoint, the armorless barbarians are cannon fodder for my Sarmatian Archers (I also have a general in Macedonia who has Cretian archers, which seem to kick ass as well...except against special forces shock troops).
I picked up two 80 stacks of Sarmatian archers, as well as some Horse Archers (OMG how I loved these in Medieval...and I do now!). Horse Archers are sweet, as they can shoot while moving, are too fast to be caught, and have way, way, way more ammo than a javelineer. Though speaking of Javelineers, I did pick up some Numidian Cavalry in my attack against Carthage. I moved in with a full stack of a General with 1 Roman Cavalry unit, and the rest Legionaries (with some reinforcements en route). After taking Carthage, I moved over to Ucidia and quickly captured it as troop sallied forth as reinforcements to a huge counter attack. I left behind 5 full stacks of Legionaries in Carthage, and they just got besieged by a HUUUGE stack. I'm hoping I can take advantage of the Large Stone Walls, and prevent them from breaking though and getting some free kills from the towers.
After taking Ucidia, I noticed another huge stack en route. Nearby, there was a medium sized stack, that also had two Elephant units. Since I hate elephants as I'm always terrified they'll run amok, I picked up the Numidian Cavalry, as well as some Rhodian slingers. The job of the Cavalry was specifically to take care of one of the elephant groups, and they did just that. I even got lucky and the last one ran amok through the Carthaginian troops, resulting in some extra kills.
I then slowly moved up, making sure to save my pila for the undoubted charge of the other elephant group. After advancing my wall of legionaries, the elephants started rushing. 4 or 5 squads started tossing their pila. I was able to get away with few casualties, though I couldn't get it to rout until it was too close. Two groups ended up losing about 20 soldiers each as the two remaining elephants went blasting through. I think proceeded to slaughter the weak Berber Javelinmen. The Rhodians had fun with them as the Berber's might as well be naked.
Good times good times.
I'm up to 55 provinces now, so I just need to collect on the ones that I need for my victory conditions (which I'm still a ways away from). Byzantium is about to fall, but I'm still a ways away from all the Middle East. Alexandria, Antioch, and Jerusalem are still a looong ways away, as is Sinope.
On the plus side, I'm starting to really pull in the money. So I have hired some diplomats to see if I can't make life a little easier on myself by paying off some cities/armies. Here's hoping I can steal a general or two! Speaking of generals, I have recently been getting a lot of adoption proposals (not that I mind). I hardly ever say no to the free, unexpected general. I have placed some of them in the small Gaul towns, so that they can take advantage of any enslavements I do. They also act as Governor's of my newly captured area in Greece/Macedonia. I'm hoping I can get some children spread from them to other towns, so I don't just feed them all from Italy.
I have 4 really sweet generals (as well as my pet project general). With the bonuses to Barbarians, two can get to 10 stars pretty easily. They just finished off Germania and are cleaning up on the Rebels in the area. I will probably land one of them in Britain as well, though the navy pirates in the area are quite a pain! But I like to conquer conquer conquer. I'm aiming for a bit of a TC Sweden and Norway will also get an axe soon too. These places do have fishing villages, so they'll eventually get ports for more money making goodness as well (though capturing Sicily was insane, as they all had at least a Shipwright. Carthage is raking in huge dough as well!)
I'm about ready to start a big push east, that will have me swallowing up the Illyrian Rebels, as well as Thrace (who is actually an ally at the moment) with Macedonia. My fleet in the Aegian Sea is getting quite large, so I may cross over into Turkey. Not sure if I'm ready to take on the Seleucids at the moment though. I'm sure they'll enjoy meeting my Legionaries!