A lot of the recent bonuses to the HRE should go. The game has become "HRE Universalis"

. Sooo many advantages for AI's that are in the HRE over AI's that are not

. I've never seen Spain form, the AI can't run Britain and has issues with France, but AI Austria is God.
Also, while the final version of In Nomine was pretty balanced, blobbing in HTTT is as bad as ever or worse. I blame "legitimacy".
New stuff:
Detail the world outside Europe. New countries (particularly in mesoAmerica and Africa), new provinces (particularly in China and India, but also in Africa), new cultures and tech groups, maybe some new trade goods (in particular, African gold should be a regular trade good and not "gold type") and new events and decisions for them. More details for colonization: rather than send one colonist and the province springs to life fully formed, have multiple stages of colonization. You (Paradox) have already built the the basic rules for the game, now add the details that make playing in those areas interesting and fun.
In general, review each major area (North America, meso-America, South America, Africa, India, China, etc.). Does it follow its historical trajectory in a typical game? If not, why not?
Revisions
Better AI. The game can always use better AI. Better peace negotiations would be useful (esp. with allies sometimes getting some of the gains).
Review National Ideas, Advisors, Decisions, Missions for play balance. The National Ideas and Advisors have stayed much the same through many changes, and, well, let's just say some are much better than others. If you can't think of a reason you'd ever take that NI or Advisor, maybe it could use some editing.
Then think about the decisions: would you take them? If not, then why should the AI? Do the countries that historically took the decisions take them, or is it just broad and general? It's always amusing to see the Barbary States ban piracy.
Think about the missions in the context of the AI: is it really a good idea for the AI to be getting this mission? For example, one game I was playing Portugal, with 150 relations and a royal marriage with much bigger Castille, and I got the mission "Attack a rival: Castille". That mission would have caused the Portuguese AI to commit suicide.
Make the "annex = yes" thing a property of an event modifier rather than attaching it to a religion. Yes, it's a good reflection of what happened to the Incas. It's also a good reflection of what happened to the Mamluks when the Ottomans took them over, or to the fate of the Ming at the hands of the Manchu, and it's not a good reflection of what happened to the Aztecs or the North American natives or the Oirat. It's not a religious thing, more a "civil war/no clear legitimate ruler + successful foreign invasion = bad" thing.
Tech level 0 countries should be able to build forts and send merchants to CoTs they know about.
The Muslim nations shouldn't start off with tech 6. If any area was ahead of Europe by 1399 it was China, not the Muslim nations that had spent the previous 50 years with Tamurlane gutting every second city. Castille consistently conquers North Africa? Review the bonuses to "legitimacy" with that in mind.