I think it would add some depth to the game if 1 - 4 small independent bandit groups would spawn throughout the game.  These wouldn't be small roving bands, they would be powerful groups with a leader that sends raids against the various cities.

The player could talk to these groups through diplomacy and pay protection fees (to be left alone) or even pay them to raid a neighbor.  Eventually when you have a large enough army the player can raid the camp to eradicate them.  There is a chance that they would respawn some where else on the map.

I'm finding that once I get behind the AI (due to poor planning or positioning) there isn't much I can do to other then get bullied by them.  Bandits would add another way for smaller empires to have some impact on the larger ones.