Sengoku Basara - Doesn't have a ton of skills like in Naruto, but the fighting is pretty good (samurai fights, but little more fantasy type) and a decent story line to it.
I think you'll like
Karas (I haven't watched it myself, haven't gotten myself to download it but I heard that the storyline is a bit confusing/short but the actual battles are hardcore epikly ownage)
Ikkitousen - lots of smackin-kickin (what I mean is lots of punchin and jabbing but no "Getsuga Tenshou!!" type looking skills, ecchi to it too; high school setting but with reincarnated warrior spirits from way back...
-way too many series IMO >_<
Gun Grave perhaps? Been a couple years since I last saw it, I do remember a few cool fights (guns and such).
Claymore - decent in fights...I guess
Fate/Stay Night - definite watch, just wish there was more "skills"; eh, but storyline is addicting....
Seems like "skilling" animes like in Naruto/Bleach are hard to come buy. Most are smack-smack or pew-pew but not really too flashy.