Caesar's fundamental misogyny will ultimately bite him in the butt, disenfranchising 50% of your labor force and creating a culture of rapine and plunder is a stupid way of empire-building. You want your soldiers to settle down and BUILD after all and there's no reason that Caesar should want women as breeding stock since the chief concern should be RESOURCES above population.
Likewise, encouraging your rulers of a Neo-Rome to be gourmet cannibals while looking the other way? It's just, ugh, Caesar really dropped the ball in a lot of places. He's created a Sparta/Hun force more than a Rome.
However, we're going to be able to test the effectiveness of Caesar's Legion more than anything by putting it up against its greatest threat. Not, as you might expect, NCR (which [SPEECH 100] the Legion military would destroy itself conquering), but the Midwestern Brotherhood of Steel. According to Fallout 3, it isn't perhaps as large and widespread as some of its endings might have suggested but it certainly seems to be powerful enough to be a force worth recknoning with.
Even more importantly, it's just as likely to serve as the opponent Caesar never saw coming.
Really, Caesar's Legion is a nice little way of explaining why the Brotherhood of Steel on the West Coast never really got in touch with our brothers in Washington D.C. or the Cheyenne Mountain area. Any brothers would have to effectively walk through two to three states worth of Legion controlled territory, of which the Hoover dam force is only a fairly mild portion of. Still, the MW Brotherhood is undoubtedly going to be aware of them eventually - they're right on their doorstep after all.
The question will be, who will win?
In the case of Caesar's Legion; they still have a supremely physical force. Like NCR, they undoubtedly will have numbers on the MWBOS. However, unlike NCR, they actively disdain technology and revert to melee weapons very often. This will be a grave disadvantage against the Brotherhood's ultra-high tech advantage.