Some ideas...
1) A pop system. It doesn't need to be as detailed as Vicky's - maybe something more like Imperator's would be more fitting, but it would be nice if populations had tangible feels. It would also be nice if provinces could produce multiple goods. This would also allow you to actually represent religious and ethnic minorities in a real way. At the very least, provinces need more texture if internal matters are to be of greater concern
2) Absolutely we need to represent different methods for taxation, as well as internal governing mechanics and interests. You wouldn't just be able to get loans from magic banks - you could also, say...sell future tax income to some nobles or enterprising merchants for a nice big chunk of change. And having all those ducats sure seems tempting, doesn't it?
Just sign on the dotted line, don't ask about what happened to Spain and France, it wasn't that bad.
This would also create an interesting tension for Muslim realms: do you convert conquered territory to make it more stable and to be better able to leverage its manpower in your armies....or do you just charge them the jizya and call it a day?
3) Bidirectional trade flow. There's no reason trade flow should be restricted: trade value should be able to flow freely between nodes in either direction, and no node should be completely isolated. Or be a black hole from which no trade value can escape, as Genoa, Venice, and the English Channel are currently. You would, of course, still restrict connections based upon geographic and nautical sense, but this would allow ahistorical trade empires to truly flex their muscle, and for European powers to squeeze every last dime from their colonial empires even if they went off the rails a little. You might; however, create a certain sense of gravity that makes it harder to pry trade out of a node in which a powerful trade empire is collecting.
4) More sensible tech. As we all know, in OTL, Europe surged ahead of the rest of the world technologically starting from the Renaissance through the invention of the Printing Press, but afterwards the rest of the world caught up and achieved tech parity, blunting European incursions into India and the East Indies. And also China remained the most technologically advanced society on the planet.
That doesn't seem right! But neither would railroading the rest of the world into hopelessly falling behind. I'm not a game designer, nor am I at all an expert on the period, so I don't know how you would do it right, but certainly I don't think it works now. For the rest of the world, the first three institutions are sinks you dump hundreds of monarch points into to surpass your neighbors and keep parity with some pale guys far away.
5) Better representation of supply lines
As we also know, the combined federation of the Pawnee, Onondaga, Mohawk, Pequot, Abanaki, and Fox crushed the first English colony like a bug, but then the English shipped their entire army of ~50,000 over the Atlantic Ocean and crushed them right back.
Oh wait, no, that's nonsense: though Indigenous peoples did frequently skirmish with European settlers in North America, to varying degrees of success, but they never won a war, so the above scenario should be an aberration. They were typically too diffuse and other nations hundreds of miles away did not march through the territory of dozens of other tribes unmolested to render aid to their brethren. More organized tribes did; however, cleave to European colonial powers in exchange for certain guarantees as to their territorial integrity (guarantees the restless colonists typically did not honor, of course) and to renew their own grudges against their rivals.
In any case, sending a large army far afield should be an expensive and difficult undertaking bedeviled by attrition and difficulty supplying them. This would encourage European powers to seek coastal footholds in far away places before launching campaigns of colonial conquest and chains of ports to help ease the difficulties of supplying distant campaigns. And encourage them to make friends with some natives. At least, for a time...
6) It should be hard to keep a large empire together
No empire lasts forever, but your average EU4 empire does, unless it runs into an even bigger, hungrier empire, of course! Nonetheless, you almost never see European countries with significant holdings in India, because the subcontinent typically consolidates into a hyper-stable collection of three or so mega-states. Ming China needs all kinds of bespoke events to get it to fall apart. The Ottomans and the Polish-Lithuanian Commonwealth rarely decline, and certainly never for the reasons they actually did. This means you never get anything like the circumstances that allowed the British to become the dominant power in the Indian subcontinent, or for Persia to rise and challenge the Ottomans for supremacy in the Middle East.