The first thing I want in another Paradox game is a diplomacy that is better. I think this is mandatory, since there is so many countries and struggles for regional or global domination.
For once, I won't take part in a (direct) debate around european history, because this is not the goal of this thread. But, like the OP, I tend to think that Europe is too powerful and that lead Castille to conquer Morocco everytime and Ottoman Empire to be almost nothing. However, I don't think the Horde system is so bad, since it represent what a nomadic tribe could be. I would see it even in Rome II or in a game about the Great invasions (or migrations, to be politically correct). I don't think, though, that Crusades and Holy Wars are so important to merit a casus belli allowing to conquer anything. In the diplomatic game, maybe the countries that are of similar religion should be tended to collaborate against a threat of another religion (even if France didn't do so, so there is limits...), but that should be handled by the diplomatic engine.
Along with my diplomatic needs, I would add that it would be great if countries were able to not attack only the infamous one, but also the big power. For if this big power patiently build conquer you, there is no difference as if a great warmongering blob conquer you, since you are dead and this country is hegemon. That would be sad for the great power built mostly peacefully, but that is the life.
I agree with the OP demand that internal maintain stability should be more challenging, but I think the concept of stability as we know it is simply too abstract, as well as the technology groups. Like one said, I think Kennedy's idea about european might could be a way to explore. If there is many struggle in an area, yet some countries powerful enough (or isolated enough, in the case of Italy) to develop other things than military, that should be a "modernization" cause (and not a trigger). Returning to the stability concept, I would like that if a general could change side, like in Rome, or if you could have a civil war (again in Rome), but please not at every generation.
About the country that hold themselves together, I think it should be considered to give to the AI an incentive to protect the land that seems to be at the heart of it and to conquer those which should be here. Altough historically some countries weren't a round blob, that was mostly because of the land (and sea) surrounding them or because an inheritence occured. Charles Quint tried to unify its empire by winning against France. Hungary, Bohemia, France, Netherland, Poland, and even Austria at the end tried to link their possessions in a logical way.
