Nam 1975
Cheap, easily available, loads of fun, good difficulty/challenge, great experience, and simply a totally awesome game. Under $40 new.
Magician Lord
Now this is just the reason graphics mattered. Compare it to say Super Mario 2, the next best thing at the time... Anyhow, great visuals, awesome music & atmosphere, evil challenge, lots of pattern memorization required as was stated, shape-changing which certainly adds new dimensions to trying to beat the game, and overall presentation that will make you a fan for life. Under $40 new, perhaps still, not entirely sure.
Samurai Shodown II
Personally I don't like it that much. In spite of that I recommend it -most people love it and as a fighter it has a hell of a lot to offer, particularly for a 1994 game. $45 new, cheaper used. Otherwise I would say go with either Sengoku 1 or 2. I somewhat prefer 2 though both are great.
Fatal Fury 3/Real Bout Fatal Fury
FF3: SNK SNK SNK. The game reeks of SNK to the very core. It's got personality. The learning curve is unsuspectingly high so you might actually spend quite a while with it. Once you learn how to play it properly you will enjoy it even more. It's also got the bonuses of hidden bosses you can only reach if you play skillfully enough and it introduced hidden SDM's. $60 and under, generally.
RBFF: It's FF3 to the next level however it's tournament fighting and hasn't got all the personalization of FF3. In any case it's also got great storyline, more fighters, an enhanced fighting system over FF3, ring-outs and more great stuff. $80 tops I would say. My only comment is that I suggest you get the FF or any series in chronological order so you don't spoil all the storylines for yourself, if you don't already know them.
The King of Fighters '94
Pretty cheap, VERY fun, and another game with a lot of SNK feel to it. Again I suggest you start with the beginning of the series. This game has a lot more to it than most people realize. You can pretty much always get it for under $50. Of course I also recommend any of the series up to '98, '97 especially.