Lets see...
Berserk: See this. It's like The Riddle of Steel as an anime, or a Grim-n-Gritty game. It's sorta dark fantasy. Some almost Cthullian elements at times. Follows the adventures of a mercenary swordsman. This has a lot of good things in it... some actual tactics here and there in the combat, the rise to fame of a mercenary or three, petty bickering amongst nobles, etc etc.
Orphen - The Scion of Sorcery: This is a semi-comedy... there are comedic elements, but it also has a harder edge underlying the whole thing. Follows a guy known as Orphen, and a couple of people who follow him. Has two of the funniest halflings known to man, though they get repetative after the first 10 episodes. See it for the serious bits, laugh at the comedy when you can. Ya get to see a lot of magic thrown about too, which is always fun.
Bastard: This is dark, but in a forced way... kinda like World of Darkness dark... This is very clearly "old school" anime... over the top fighting, every male character is muscled like a WWF wrestler, etc... but it's still worth seeing. The character of Dark Schnider is rather interesting. The world is kinda unique too.
Slayers: Um. Duh

Slayers has to be seen. It's comedy, no mistake. But it's very GOOD comedy. And it's fantasy comedy to boot. There are three complete seasons (Slayers, Slayers: Next, and Slayers: Try), some OAVs, and a handfull of movies (Not all of which are out in America yet)... I'd suggest starting with the first season, and going from there.
Now, for some slight variations on the theme--
"Samurai X": Not it's real name, but for some reason that's what it got called in America... it's a two-disc or two-tape series... Trust and Betrayal... It's set japan around the Meji Revolution. Slightly over-the-top combat at times, but not too bad. Very powerful and moving.
Hakkenden: Legend of the Dog Warriors - Very... deep, I guess. This is a box-set type deal, three discs in the set... It's I think 12 episodes long. Based off an old japanese novel. It's a fantasy series, make no mistake. Magic swords, demons, change-childs, etc. Well worth seeing, but not for... for the weak-willed, I suppose. There are a few points where it slows down pretty bad, kinda like in the original Lodoss series. But if you stick with it, it's worth seeing.