Ok, I know the idea of Medieval 3 has been beaten to death and the creators have apparently said they aren't planning on doing any large scale #3 rehashes, BUT I think recent games have opened up some awesome ideas to make a truly stellar Medieval game.
Firstly, roughly overlapping the age of Charlemagne timeline and using the same quests such as creating the one nation by conquering several. I always thought that was a very cool idea of conquering these specific areas to create a larger kingdom. Another great idea (in my mind) would be to take the character mechanics from Three Kingdoms where rather than simply controlling one large central army you have a central army that you own but much of the power comes from alliances or vassalage from other nobles and knights. This would be much more accurate as a king would "call his banners" and the nobles would come with their armies. It would also mean keeping peace between nobles in your own kingdom. Using this political aspect of feudalism could make a truly legendary medieval game.. though unfortunately it sounds like no large scale Medieval 3 will ever come to pass unless the demand from the fan base becomes big enough.