Honestly, just a few automation methods stuck into the UI would have done a... lot. Loopable building queues (which part of would be pre-setting commanders, what they're leading, and orders. This would also incorporate summons on all levels.), multi-province move orders (waypoint/rally commands), auto-site search, auto-scout (possible auto-assassinate!), nation wide order changing (say I want to change 1/3rd my <casters> to one set of spells, 1/2 to a different one, and the rest to something else, in one go or have all my <commanders> with >X units or leading Y unit type start moving towards province <whatever>... stuff like that)... just general tedium/micro removal. Don't even have to simplify the systems involved, just the means of using them.
My biggest complaint with Dom 3 has always been that it doesn't really give you the toolset to elegantly manage the game later on -- it's not that a toolset couldn't be made to do so, it's just that there wasn't one. Dom 3's biggest problem is UI.
Sideline a few things to encourage mid-late game usage (continued searching, etc. Make sites synergistic on a nation level somehow, so every extra one adds something potentially useful/possibly gamechanging instead of just more gems, stuff like that.) and it'd clean up the game a lot without having to sacrifice complexity or introduce more limitations.