Since TW has already visited the medieval time period twice, a closer look at Feudalism would make the game more distinct yet still be set in this very popular time period. The earlier Medieval games were based around 1080-1500 A.D. I think a game based on feudalism around 850-1250 that brought the unique age to life more so than the earlier TW games would be highly successful.

Instead of being a renaissance type absolute King of an entire Kingdom, each player would start as a Feudal Lord King who needed the cooperate with his Lords to accomplish larger goals. The lower Lord's loyalty rating towards you [based on your actions] would determine the tax money and recruits you received from them. You would have your own royal army and could expand especially aginst single cities or castles, but it would not be the entire realms army. So wars would be much smaller in scale for the most part. Larger wars between whole Kingdoms would only come about if you were able to get the support of your lords under you. If you taxed them to much or don't allow them autonomy, they would be less likely to lend support and might even rebel against you. Lords normally would contribute money or men to the crown but if you need more you might call for muster. A particular Lord who usually gives good support holds back this time leaving you in a bind. Or perhaps a Lord lends more than usual. However the more you muster the less that Lord has for defense if attacked. He might be calling on you for help if you muster to much of his forces.

You could receive missions from Lords to improve your standing with them or ignore them and it would hurt your standing with them. Likewise, a powerful Lord of another Kingdom might give you a mission to work to dethrone the king of another realm. Lords would be more independent, some might go on crusade with you or refuse to follow you as King if you go. The peasants might be having trouble with a Lord and ask you for help, do you join the peasants or the Lord? how would that affect your reputation?