Talysia
Lady of Autumn
Admittedly, I didn't watch all of Record of Lodoss War, either. The storyline jumped around far too much, and characters popped in and out from everywhere. I enjoyed it once I'd figured out how it worked, though. Legend of Crystania (the sequel) wasn't much better, but at least they set the scene for more fantasy stories to be written/animated in Japan, or at least to become more mainstream.