It's not really about complexity, if we want to change thing similar to what we did in Civ4, and since Civ5 is now about positional combat and not +/- vs type combat, we need to find way to have the same depth as before, and get even closer to real ancient tactics and warfare, but still make it "TAM Fun"(tm). For example, a late Mobility promotion that allows to move after attack (so that you can fall back), Hold the Line promotion that gives bonus to units around you, a Skirmisher one that allows light units to stack as a non-combat unit (only one combat + one non-combat can be on a Tile in Civ5, so we're not reintroducing stacking really), etc. They could come from XP or buildings. These aren't huge changes, since the new combat system is a lot closer to what we envisioned in Civ4.
Anyway, we'll have to talk about it in more details and tests the possibilities, these are mostly just ideas that popped into my head.
Also some notes and ideas I had when playing Civ5:
We need to reduce unit type and space them a lot. We want ancient combat combat to be focused on archers and chariots, classical combat with Hoplites, and so on. Promotions would differentiate tactics and such instead of unit types. One or 2 unit type per eras is enough. Swordsman/axeman/maceman/spearman are mostly infantry with diff. weapons and tactics, that could be differenced by promotions and buildings in your cities. That's the difference between a simple spearman and a trained hoplite with specialized equipment.
Since not many civ really had a standing army before the marcus reform, and armies were raised from citizens and wealth, we might want to look at how we could do it in Civ5. Now that everything is about wealth and gold, mostly, this could be actually easier to do than in Civ4 with the conscription option. Richer civs would raise bigger armies, others would need to have better individual units to survive, kind like achaean league vs aetolian league. As I've said before, Mercenaries could be something interesting too, you could recruit from military City States instead of receiving automatic units when they are neutral.
We could make greek cities as City States and make Macedonia the playable Civ. If we make the map big enough, we could have Athens, Delphi, Thebes, Sparta and Corinth as City States that you could ally with, conquer or such. We could make City States more active, declaring wars against each others, allying themselves, and so on.
Also, an idea, maybe being able to settle a City State instead of a normal city, that costs nothing in term of happiness, you gain resources and you'd start as allies, but that could change over time. You could probably release them as independent, or take over later. This would simulate Colonies and such, which is pretty important for Greece and Phoenicia. Or, city states could build settlers and settle but it would create another allied City State...
BTW, should we use the mailing list for Civ5 dev, create another one? I could setup a dev wiki for the team, a place for source control (to make the integrator's life easier and between contributors), a place to track issues and suggestions, etc. Maybe I'm too eager and jumping the gun a bit tho...