MY PERSONAL RECOMMENDATIONS!
Project Justice: the sequel to Rival Schools: United by Fate, this game is absolute perfection, if you like Capcom's fighting games so this one is pretty much required! Really fun 3v3 fighting game with a great cast of characters, great music, really pretty graphics and a very interesting story mode. I love this game and I highly recommend it.
Fighting Vipers 2: sequel to Fighting Vipers, and it's just as good as the first game, if you like Virtua Fighter than this one is just as great \o\
Tech Romancer: spiritual successor to Cyberbots, this game is a odd mix of several giant robots based on different categories of mecha anime (Super Robots, Real Robots, Magical Girl, Ultraman), and I love it. The story mode is REALLY in-depth as well, with a lot of different routes for the characters, the game is really fun in general, and you can even unlock Jin Saotome from Cyberbots as well!
Street Fighter Alpha 3: come on. It's Street Fighter Alpha 3. You know you want more Alpha 3 :V
The Dreamcast has a LOT of great fighting games, this is just the tip of the iceberg xD