Keep stacks, but give them penalties for exceeding sizes of 20, like -10% defense, but growing as the number increases, which would make picking off siege with low numbers of cavalry types easier. Similarly, give combined arms bonuses for having 10-15 units of +10% on defense as long as there is at least 3 different types of units, to give an optimalish of not-too-many units in one stack. This bonus might depend on unlocking it from a relatively early tech (Rome, Greece and Persia all used combined arms). Great Generals would raise the limits of both of these by some amount (3? 5?)
More bonuses and maluses for combat: Stacks size ones just mentioned; attacking from the west gives +3%; attacking from the east gives -3% (sun in eyes... does make assumption it's always morning when attacks happen, but is generally historically the case); cavalry attacking from a hill into a plain -10% (horses have troubles running down hills); defending a riverred tile from the same side as the unit attacking it -10% without amphibious (pinned against the river); same but lesser for attacking a unit adjacent to a hill or mountain (pinned-ish by hill and mountain); attacking from walled/castled city into stack of any size greater than 1 -10% (bottleneck leaving the gates); etc.
More bonuses for being the first to techs. Not great people or the like, but just for units. First to construction/engineering/steel? All your catapults/trebs/cannons get drill 1. etc. This could instead entirely be replaced by the suggestion below:
More military techs, that sort of follow their own specific trees, like Military Science and Military tradition, but throughout the tech tree. They could even be as simply named as Military Science 1 MS2 etc, though names like "heavy catapults" for improved cats or "shrapnel cases" for cannons would be better. If you want to "waste" beakers on techs that specifically improve military units but lead to no other techs by going after military science you could get bonuses to your current units (which is why I say like MT and MS; better units, but complete dead-ends on the tree). these techs would still be tradeable of course, which would reduce their dead-endedness, but when you go after them, you probably DON'T want to trade them.
Hexes.
Spherical Map.
Better Land-unit-to-sea-unit movement rates, even if that makes sea units crazy fast (though you have to remember that modern navies are actually kind of slow, so top-end rail-based movement actually should be faster).
More integrated tech/unit combos. Ex: Swordsmen start at Str 5 say, but are build-able at bronze working, but get str 6 at iron, and get str 6.5 at machinery, and str 7.5 if they are somehow still kicking around at steel etc.
Better balance of civics.
Running slavery causes you to take over enemy cities at size one, but now you have slave units that you can bring back as crappy super-specialists (+1 hammer?) until you jump out of slavery. Alternatively, you can use them as "free" whips, but this pisses off the civ you just took the slaves from and any civs that are friendly (not pleased) with that civ. (You worked our people to death! -1 and You are a genocidal maniac! -1). The penalties should cap out somewhere though.
More techs. Slower to top-end techs.
Cheaper units (hammers and gold) for more frequent, even if mostly pointless wars.
Elimination of cheesy victories. AP win definitely gone/completely reworked. Space more expensive, which combined with cheaper units will make it more difficult. Culture victory gone, but culture causes immigration which reduces the higher-culture civ's food cost for more pop, and gives free happiness to support that extra pop. Being at the receiving end of the higher culture makes it take more food. This makes culture still useful without it being a joke win. Similarly, there should be civic choices to try and stop the tide of immigration, but this causes diplo maluses and hurts trade (à la North Korea and similar isolated societies).
Friendly is harder to get to (for everyone, even AI to AI) but it means more if you can get there (like if you got daggered, you could ask for help and probably get it from some 3rd party friendly civ without giving away the kitchen sink).
I'm sure I could think of more given more time, but those are the big ones for me. More combat effects, more dynamic unit strengths through improved techs, more dead-end techs that are for a "right now" bonus, and elimination/reworking of "crappy" wins while still maintaining uses for culture.