I would very much like to see possibilities of shared control of a region. For example, if player A colonizes a region (with, say, a trade colony or a military post), this should not necessarily mean that he controls all of it. There should be the opportunity to try and monopolize businesses in other factions' territories. Being able to establish trade networks (with the possibility to fortify them, like the Varangians did) in "foreign" provinces would also be great.
Also, some representation of how a faction takes over a province: whether it's only taking over the government, or making them a client kingdom, or a full scale invasion of a whole people, or even marginalizing/wiping out the natives and establishing a new population/culture.
Speaking of cultures, there should also be a way to determine whether you (as the player culture) adopt the native culture, or the natives adopt yours, or there is a mix between the two.
Another major request of mine would be having a third weapon for cavalry units (and maybe for infantry too). That way, we could have mounted Samurai carry and use a bow, spear, and sword like they historically did, or an European mounted knight with a lance, sword and mace. There could be an automatic system that determines which weapon is most useful against which enemy, as well as a manual setting, if the unit in question has more than one close combat weapon.
Also, I'd very much appreciate the possibility to win the game without constant all-out war (i.e. without having to fight an unrealistic number of wars and battles). Be it via diplomacy or sabotage or whatever else. Other than that, I can only reiterate the calls for more historical accuracy and easier moddability.