An RTS called Praetorians for the PC. It was a stratagy game with a good single player which you played as Romans in a neat little story.
It had a fantastic multiplayer which you could play as either Romans, Barbarians or Egyptians which all had a variety of different units with strengths and weaknesses. And with the patch there were 3 more races to chose from although they were kind of mix and matches of the first 3.
I would be surprised if anyone here actually played that game. It consumed hours of my childhood.
EDIT: Actually I have to thank the OP. This has given me some of the best nostalgia ever. I remember that this game have fantastic cinematics and a fantastic soundtrack. Hell when main menu music sounds this good it can only be great.