Welcome to the world of anime, ddymor. Just as with any other medium, there's good anime out there, and really bad anime out there.
My recommendations...
Record of Lodoss War: This anime has a very D&Dish feel to as, and it should considering that it's based on the creator's D&D campaign he ran while in high school. Lots of fun, especially if you're a fan of fantasy RPGs. The characters tend to adhere to classic D&D archaetypes (such as the dwarf fighter and the wisecracking thief), but are memorable nonetheless. And, even though I don't usually drool over anime girls, I can say with complete honesty that
Pirotess, the evil dark elf woman, is one of the sexist female character designs I've ever seen.
Cowboy Bebop: This series is just plain fantastic. It's a space opera that combines elements from noir and 1970s blaxploitation films, with memorable characters and an absolutely fantastic soundtrack. Truly a must-see!
Tenchi Muyo: A rather strange series where a Japanese high school student awakens a demoness (who looks like a beautiful woman, of course) from a cave near his home, which sets into motion a chain of events that results in him sharing a house with several woman from across the galaxy. Despite the strange premise, the series manages to remain enjoyable due to the memorable characters and great comedic moments. 13 episodes were produced for this series back in the early 1990s, and only recently the series has started up again. However, I reccomend that you stick with the original 13 episodes, because the new episodes are disappointing and fail to capture what made the original episodes so special.
Berserk: I haven't seen this series all the way through yet, but what I have seen was absolutely awesome. This is another series set in a fantasy medieval Europe-type setting, but it's a very dark and violent series (I've heard it described as Record of Lodoss War meets Conan the Barbarian). The series revolves around a guy named Gatts, a mercenary swordsman who is a muscle-bound, scarred, ugly lump of a man (a big departure from the effeminate pretty-boy heroes found in many other anime series) and his adventures in a brutal, war-torn world. I hope to see the rest of the series soon.
I'm going to go against the above poster, however, and recommend
against Neon Genesis Evangelion; I decided to watch that series just to see what all the hubub was about, and found it to be pretentious, confusing, and self-indulgent. You couldn't pay me to watch it again.