Europa Universalis is probably my favourite of all the Paradox titles. That said, I think it's reached a stage that to move forward a new iteration is necessary that sheds a lot of the baggage that's been present since EU1 and 2, and brings the focus on what makes Europa Universalis as great a game as it's always been. I hope Paradox will find the ideas in my post of interest. The following stands out to me:
1. Make countries feel like they're being role played. In vanilla EU3 countries felt too similiar to one another, while that improved in subsequent expansions, it never was completely solved. Every country and region in game should have it's own unique character, but most importantly, over the 3-4 hundred year course of the game the player should be able to mold it to exactly what they desire, be it an aggressive theocratic state, a sprawling colonial superpower, a small but very innovative mercantile power, or whatever a player might like. At the same time players should not able to do absolutely everything. They should have to pick their strengths. The national idea/slider system was good, but there were some weaknesses.
2. Play through the ages, each era should feel a little different from the last. While this works well in the early game (For instance you have the reformation throwing a spanner in the works early-mid game), the later parts of the game all feel samey.
3. Change technology, the current system where you just pour in money doesn't feel right at all. Technology should perhaps work more like Crusader Kings, with spreading developments (if one country gets arquebuses, the technology should quickly spread to it's neighbours), rate of development more related to social structure and ingame variables, rather then coded geographical numerical factors. IE China should develop more slowly (or not at all) because of it's it's social factors and isolationist political outlook, and not because it's in an Asian techgroup. Also, it should be possible to move "backwards" under specific circumstances. Perhaps there should be a split between technological innovations (things like the printing press, cannon), practical capabilities (I know about cannon, but do I have the gunsmiths to make them? Do my officer corps have the tactics to use cannon effectively?) and societal factors (Do I have a society where new ideas can flourish? Are the aspirations of my people incompatible with the way my government is organised?)
4. Reduce era bloat: Europa Universalis should focus on one era (roughly the Renaissance, Reformation, Age of Colonialism and Enlightenment) rather then moving into the middle ages on one side, or the napoleonic period on the other. There are now games that more then adequately address those time periods (namely Crusader Kings, and the in-development March of the Eagles).
5. End the "blob" problem: The primary issue with EU, for me anyway, is that I've basically "won" the game by 1550, having grown to such a size that no other country (or coalition of countries) could possibly oppose me. This is a sticky issue, and is a central problem for all grand strategy games. As far as I can see, it can be solved in 2 ways:
5a. Change AI diplomacy, Medium sized AI should band together to defeat large neighbours. So Sweden and France should join together to defeat a blobbing Austria, France should have trouble getting any alliances among it's neighbours, due to how powerful it is. Very powerful countries should be unable to get alliances outside their sphere of influence and vassals.
5b. Change rebels. Rebels are currently a speedbump rather then a real problems. Players should find it increasingly difficult (without being tedious) to control a large state. Large Empires should have to adopt ideas oriented towards stability to even stay together, which may cause them to fall behind other, "leaner" powers. A country could have a variety of approaches from federalism, to an absolutist conservative state ideology, both of which hobble the player in a realistic fashion. In addition, civil wars should be a real threat, and rebels should tend to rise up all at once, rather then peacemeal.
In this way, China, or player led blobs, could be held back without resorting to crude "cheats".
5. Speaking of Diplomacy, end the mystery of diplomacy. Instead of the current "floating" values, switch to the static values Crusader Kings uses, and have each AI response be yes or no (and no "likely"s or "maybe"s), with reasons shown for why or why not the AI responds in a particular way.
6. Trade: One universal market price seems crude, instead the price for spices should be different in Lisbon and Goa, and the profit from trade should be from exploiting those price differences.
7. Piracy: Rather then being units you quash at sea, they should be an issue that exists at the provincial level, and, more importantly, effects trade routes. Tariffs represent this quite nicely already, and could be extended.
8. Revamp colonies: Once a colony reaches 1000 people, it behaves just like any other province, when in reality the colonies took 100 years or more to develop, until they reached a stage whereby they felt they should fight for their independence from the crown. This aspect should be depicted ingame. Also, colonialism was much slower in real life then in game, Jamestown was only established in 1607, by the same date in game most of the US east of the missipi has been colonised.
9. Revamp stability: Stability should be the result of all the myriad factors in game (somewhat like in Vicky), rather then a static number that gets changed by pumping money into a stability bar. Instead, if you're a conservative monarchy ruling a populace filled with liberal revolutionary ideas, the player should be thinking "Maybe I'm due for a revolution...". Likewise, another monarch's heir could have a weak heir, prompting a period of chaos and civil war when he comes to the throne. In addition, foreign powers should be able to involve themselves in the civil wars of larger countries.
10 Reduce the feature creep: EU3 has a lot of disjointed features that need to be tied together more. One previous poster noted that cultural tradition and military tradition were handled on one screen, and could perhaps be integrated together more seamlessly.
11. Address the entire world outside of Europe from the beginning: In particular address the Middle East, India, East Asia and the New World. PDS is a much bigger company then it was back when EU2 was made, or even EU3, and I'm sure you'd be up for the task. And when addressing these regions, make sure that ultimately you're playing by the same rules as European countries. It should be possible(albeit difficult) to guide an asian country to be an innovative and advanced society, while a country in Europe could (particularly under player direction) sink into being a backwards isolationist society. The factors that led to these outcomes should be reflected ingame.
12. More historical immersion: I'd like it if the art and culture of the period was featured more prominently. For instance, much as I like the original music of EU3, the classical music of EU2 (especially as the game went on), gave the game a certain sense of immersion and authenticity. I'm sure there are classical orchestras willing to license out their recordings for cheap.