Kagus: Agincourt is particularly difficult. It takes some replaying to win and if you get it the first time, it's quite impressive. That's why it's one of history's more legendary battles. Basically, you just need to turtle and rely on your longbowmen while shifting your other units to cover them.
There's a very deep battle mechanic in Medieval. For example, if you position your units around 10 meters in front of your archers, your archers can fire straight forward, over their heads, instead of lobbing shots in a high arc. Also, if you are fighting against highly mobile or lightly armoured foes, you might want to switch to non-firey missiles for faster shots.
Also, it's quite imperative to discern how deep you want your ranks to be. If your spear line is too thin, the enemy can actually pierce it and punch through (The AI will sometimes do this) but if it's too think, they will just flank you.
I highly recommend the Total War series. I recommend it over Civilization. Simply because it maintains a lot of the aspects that made Civilization fun and then allows you to control your armies yourself (with the super deep, realisitc and engrossing battle mechanics) instead of relying on random results. In fact, you'll probably be spending more time on the world map instead of in battle. The Civilization-esque mechanics are quite superb. This is one of those games (kinda like DF) where whenever you lose a battle in the campaign (i.e: sandbox take over the world mode), you can only fault yourself. Not the stupidity where your aircraft carrier was sunk by an ironclad.
Hrm... there's a lot of things I love about it that I didn't mention here:
1. Each and every single one of your royal family members have their own stats, characteristics, and basically... is like an individual RPG character. They will grow and develop and you will be quite depressed when your awesome king of ultimate dreadness who singlehandedly conquered France dies of old age.
2. So many units. Insane. They're all basically the same but when it comes down to it, you can really tell the difference between those Polish nobles and your own Cuman Horse Archers.
3. Lengthy, lengthy descriptive flavour text for your viewing pleasure. EVERYWHERE.
4. Voice acting and speeches are brilliant. The over-the-top-ness doesn't reach the level of cheese like say... C&C, but it's damn good. I've played the game for over 400 hours and apparently I still haven't heard all the speeches the generals give before battle yet.
5. Huge battles. Massive. Want to recreate the defense of Helm's Deep? Go ahead.
6. Tactics play a huge part in gameplay. It's so important that if you're one of those who can't understand why it's silly to stand ON a bridge to defend it, you better not play this. If you're one of those who love to scheme and pretend to be generals, you'll love this. When your army of 300 defeats a 2000-strong force through clever use of strategy, terrain, cover, weather, and mobility, you will run around your house screaming in joy. (The game will mark all your incredible battles by putting a little sigil where it took place, detailing what happened)
Yeah, I really like the game. I'm really looking forward to Empire: Total War.
edit: It also reminds me of one time where my English forces were sieging a Scottish fortress. I had brought about a huge army consisting only of heavy knights, intent on just steamrolling them. I also had one group of militia spearmen accompanying them so they could man the battering ram to breach the gates.
It was all well and good until my spearmen reached the gates with the battering ram. What happened was the Scots charged out of the gates in that very instant, slaughtered my poor militia spearmen, then ran back inside. Now my army was stuck outside and the Scots were laughing their arses off.