Need help finding an adventurous anime

[WaffleZ]

I'm a bit specific in terms of my taste, and I just got out of my mecha phase, so now I'm looking for a good anime set in medieval times. Or some sort of universe parallel to medieval times.

Here's my list of criteria:
-Set in medieval Europe (or a universe that parallels that)
-Has your usual type of characters you'd find in some sort of RPG (swordsman, mage, rouge, archer... that sort of nonsense)
-Maybe has some sort of war plot in it.
-Characters aren't stuck in God mode where they can run super fast, swing a sword 50,000 times in the blink of an eye or level a building with a single swing. (This one is going to cross a LOT of animes off the list)
-Good fight scenes. :3

Don't suggest Zero No Tsukaima or Claymore- because I've already watched those two. (Really liked them by the way.)



The closest anime to what I've described is Tears to Tiara. Which, while it had a great storyline, interesting characters and simply amazing combat scenes- I just couldn't get into. Why? Because they made EVERYTHING revolve around a main character whom you just have no reason to care about. They don't elaborate on his character at all.

But given my key points of interest, can anyone recommend a good anime to me that follows those guidelines?

Oh, and blood. I like blood.
...And yes, I've watched Berserk.

[Silent_Darkness]

I know I loved that one to. The one I recomend Shaman King but you don't get adventures until a few episodes later.

[Autumn Demon]

utawarerumono

[Kleo Scanti]

Record of Lodoss War is quite old, but it fits into your description very well.

[AnimeFangirl]

Guin Saga and Juuni Kokki. Oh, and Seirei no Moribito. There are a few super powers in each one, but nobody levels buildings with single swings.