I super duper recommend the Bushido Blade games as well. I have forced almost all of my friends to play them with me and the consensus is that they're super neat but really janky and hard to control. x) Still, give 'em a try! They are flawed gems, but still gems. Thankfully, indie games have kept the formula alive, even if they are rather different. Nidhogg 1&2, Hellish Quart, One Strike and Slice, Dice & Rice. No doubt there's more, but that's a start.
I third the Bloody Roar games as well, especially 2. They aren't good in the sense that you'll never see them at Evo, but it's one of my favorite fighting game series. If you end up liking the PS1 games, Bloody Roar: Primal Fury for the GameCube is the best of the series. Bloody Roar 4 kinda shitted up the series by making your transformation bar count as your health meter while transformed, but it's not a dreadful game. It did kill the series off though. x)