Quite personally I'd like to see traits again return on how you choose to use them in battle and city governorship, and just random traits. This gave a lot of personality. This died in Empire and the ability to pick traits and retinue were things I didn't like in Shogun 2.
Get rid of all ahistoric nonsense. No Head Hurlers or Screeching Women. I guess I'd be fine with some fun stuff, but as easter eggs.
I liked the "Families" system used in Rome, but maybe instead of making them all different colors, make them different shades of red or some other color?
Obviously more factions, no rebels.
Deeper Africa, map extending to India. China might be a bit of a stretch though.