Internal factions and proper civil wars.
This would be enough to make it truly EU4.
Some minor modifications to Africa and Amerindian nations. No overhauls, but they need to be able to field muskets without westernizing. A couple of modifiers and decisions should be enough.
Internal factions would be really interesting, maybe something akin to the movements or the upper house in Victoria 2/AHD.
Some kind of overhaul to the AI deciding which side to join in a war should be done too. I was playing EU3 the other day as a Delhi that had conquered maybe 85% of the Indian subcontinent and declared war on Khandesh, which at this point had been reduced to a one-province minor. Bengal was allied with both of us. I had fought by Bengals side in half a dozen wars, protecting them from being wiped out by Deva Bengal and the SE Asian states beyond, even selling them provinces at no cost to make sure they have the land necessary to keep them alive. Khandesh, once again, was a single province, surrounded by me, of literally no importance. Bengal decided to side with them and declared war on me. -_- I don't know what exactly can be done to fix things like that, but it's probably worth taking a look at.