-Limited Casus Belli:
For example a Trade Dispute CB could only gives you a few overseas provinces or remove embargo...but cannot allow you to swallow of the country you're attacking. Another example would be a reconquest Casus belli that only allows you to take the CB provinces. Or colonial CB that only allows you to take or asiege overseas provinces.
-New Peace options:
Like you can remplace the current dynasty by one more friendly to you (well, random dynasty again, just that the country has +200 relations with you but suffers revolts for some years, because of legitmicay and such).
-Making it harder to convert:
Only for heretics it should be as easy as it was in EU3, otherwise, it should be hard to convert provinces (apart the pagan ones). I'm tired of Ottomans mass-converting the Balkans by 1410, or Castille doing the same in North Africa
-Making it harder to colonize:
Maybe adding a technology/tech group modifier to colonization. For example, in Africa, chance for colonization shall be only of 10% at most, until 1750...unless you're in the african techgroup, then colonization is easier. Same goes for South America: Hard to colonize before 1500, unless you're in the Native techgroup. It would help keeping certain regions free of colonization for decades, like Africa.
-African Slave bonus
more colonial growth if you produce slaves or trade in them.
-No more crusades
Because Castille can into Egypt by 1420... Though we should keep holy war CB (it's normal it doesn't cost much infamy for European nations to invade infidels). Hopefully, with much more harder conversion, it's quite a pain to keep those muslims provinces. But less incentive to attack muslim nations is better.
-Make overextension a killer
It shall be as dangerous as being over infamy limit... Seriously, something that makes you think twice before blobbing
-No more Wastelands:
Make them really really poor provinces (0 base tax, 0 manpower) with shitty ressources (Wool or Grain). It shall represents the fact that even if some Europeans can colonize as far as Far west in North america, it cannot be developped without railroads or more modern techonlogies. But at least we can go across them...
or we can go across wastelands, but not colonize them
I mostly think about the passage between Mali and Morocco, across the sahara... Seriously, ok you can make people pass through there, but then, there shall not be any wasteland in any other part of the world.
-Redo the technology system, maybe more like Vicky or HoI.
-Reform the Hordes!!
the Always at war system is nice, and so is the few diplomatic options. But the when the game start in 1400, the hordes are already past their glory... they shall not be able to conquer, unless they use a special horde conquest CB (given under special conditions, like +3 stability, etc). Instead of the classic conquest, an horde could get more bonuses (like some ducats) for controlling a province under normal circonstances. Maybe it also add a "ravaged" modifier to the province (a bit like scorch the lands) so for normal countries, you try to do your best not to be invaded by Hordes, even if they can't take provinces under normal circonstances. It would show that those nomads were more doing Raids than real conquests at that time.
-Can't remove provinces from HRE if they're not your cores.
That will stop non-HRE countries from blobbing inside the HRE once they're stronger the emperor...because of those maluses.
-Make it more problematic to goes past sliders limits
Ah well, I'm sure I can find other things to say, but I'm out of ideas for now...