Internal country matters - factions, faction demands, reactions to diplomatic or economic events, internal struggle for power, better civil wars and realistic rebels, etc. I'm tired of just expanding with homogenous country, I want to make my country prosper and actually see, how it prospers.
Religious minorities - province does not have one universal religion. I'd like to see conversion shifting the balance, sometimes achieving it's goal, sometimes failing, sometimes provoking violent reaction
Economy & production - province does not produce only one good, but larger variety of goods in different amounts...Also separated income from factions (cities, nobility, church...) based on their strength and prosperity
Trade - I'd like to see dynamic trade routes. They had tremendous impact on diplomacy (Silk route, Spice route) and province wealth. Maybe to add "route security" - bandits influencing income form particular route etc.
Diplomacy - Coalitions and defensive alliances, alliances against particular country etc.
Colonization - adding trade posts, ability to colonize undeveloped nations provinces, colonial "diplomacy"...
Military - something like Magna Mundi had would be awesome