You already mentioned the Metal Slug games and Samurai Showdown 2. Great games. I also enjoyed The Last Blade 2.
For me many of the late 90s King Of Fighters are worth it. I played 98, 99 and 2000 quite a bit... those are the ones that showed up in the arcades when I was in high school. I have a special place in my heart for KoF 99, but I know that is somewhat of an unpopular choice of KoF. Also Garou: Mark of the Wolves.
I had a great time playing Money Idol Exchanger with a friend. I also liked Magical Drop 3.
Windjammers also was a lot of fun.