Vampire Hunter D is so awesome. I was a bit skeptical of it at first, but it's got some really cool scenes in it, very well made. In my opinion. But I say go for it.

Rurouni Kenshin is pretty good too, but I think Trigun is better. You might like that. Or you could check out Samurai Champloo.

Ah, anime.