Super Street Fighter II. Not the Turbo version, not the ultimate version, but the first version that came out (bringing in the new four characters, Fei Long, Cammy, Dee Jay, and T. Hawk). I still almost always used Ryu, and had much fun frustrating people by constantly bombarding them with fireballs. Not many people out there could consistently blast away with fireballs, and people who tried to get into fireball wars with me almost always ended up losing.
Samaurai Shodan II. I enjoyed using Genjuro. One of my roommates always used Haohmaru (yes, we had a Neo Geo), and the battles between us were the classical type, where there were very few exchanges of sword slashes, but the few exchanges were always deadly. Contrast this to other people, who would constantly mash away at buttons all throughout the round.
The ancient "Yie-Ar Kung Fu," where you controlled a fighter named "Oolong," and could bust off a large number of punches and kicks, while also being able to jump 50 feet in the air (no joking). Didn't take much skill to defeat the first few enemies, and in all honesty, anyone who lost to the fat gas bag known as "Buchu" needed some lessons in basic dexterity. The most frustrating enemies on that game were Sword (until I found his weakness versus the low kick) and Tonfun (curse those quick multiple strikes).
The ancient "Karate Champ," where you had two joysticks, and could choose a multitude of moves using different combinations of those joysticks. One hit = knockdown... God help you if you tried to play any of the computer game ports, where trying to use a joystick with a single button was an excercise in frustration.