I got Mount & Blade at Stush's recommendation, and I'm finding it pretty engaging. Here is a mediaeval game with a Frontier: Elite II level of freedom, and at the same time this very personal and realistic level of power.
Two things so far impress me about the game. First is its great flexibility. You're not tied to a role; you're simply a man on a horse with a sword, and from there you can do whatever you feel like. You might travel from village to village and raise a peasant army, or trade spices and furs with distant towns, or enter the service of a local lord as a mercenary captain, or protect the land from bandits, or become a bandit yourself. If you take defeated bandits prisoner you can ransom them off, sell them into slavery or recruit them into your own army, and so on.
The second thing I like is the combat system. There's no Total War style point-and-clicking, no pausing the game to examine the battlefield and issue orders. You control one man, fight by aiming your sword, block by raising your shield, and issue orders by shouting. Your army is made of whoever you can find by yourself and pay for with your own gold. The combat system is cumbersome and challenging, but plenty of fun, and this makes it incredibly rewarding to get a handle on.