If you want more fighters, here's what's still not in the States. The ones in bold are the best:
-
Garou Mark Of The Wolves-
Fatal Fury Battle Archives 2 (contains all the AWESOME Real Bout games)
-KOF Orochi Collection ('95-'97)
-KOF NESTS Collection ('99-2001)
-KOF Neowave (The Japanese PS2 version has two more characters)
-
Vampire Darkstalkers Collection (All the Darkstalkers games)
-
The Rumblefish-
Arcana Heart (this has been picked up by Atlus, but the import is only $30 now)
-
Hokuto No Ken (Arc System Works' Fist of The Northstar fighter. Think Guilty Gear)
-
KOF Maximum Impact Regulation A (An improved MI2; lower-priced and awesome)
-Fu'un Super Combo (Savage Reign and Kizuna Encounter)
-
Melty Blood Act Cadenza (doujin-fighter-turned-arcade game, full of chains n' air combo craziness)
KOF '98 Ultimate Match will be getting a PS2 port, too. The game is hitting arcades in March or April. Because of that, there's really not much of a reason to get Neowave or even the collections in my opinion.
Other stuff:
-
SENGOKU BASARA 2: This is Capcom's take on Koei's Samurai Warriors games. It's more over-the-top, flashier, and more like an arcade beat-em-up crossed with a Musou game, with smaller, linear stages, but more enemy variety and bosses to take on. Just an awesome, awesome game all around, and what's even better is that if you like this, there's Sengoku Basara 2 Heroes, an expansion with more campaigns, playable characters, and levels.

Heroes also has 2P split screen play.
-Twinkle Star Sprites La Petite Princess: A 3D remake of the Neo-Geo vertical 2P split-screen competitive shooter. Also contains the original version.
-OZ: Interesting beat-em-up from Konami that revolves around juggling. I picked this up some time ago but really haven't spent much time with it yet...can anyone else here shed more light on it?
Virtua Fighter 4 Final Tuned never got a home release, by the way.