Super Street Fight 2: Turbo was, I believe, the first fighting game I've ever had on while I was holding the controller and moving the character. I think I picked Dee Jay, Ken, and Cammy (I had to have been 4 or something at the time). Don't know if that counts as an experience, though, so I'll keep going.
I also remember playing X-Men: Children of the Atom (that, and Marvel Super Heroes, but the following description matches them both). To me at the time I didn't really register it as a fighting game, though, it was just that game with all the cool super heroes in it (my family is big time in the nerd realm, from Forgotten Realms to Earth-616 to the Final Frontier). So I don't think that counts either (probably 5 or 6 at the time). Moving on.
I played Killer Instinct Gold or whatever, on the N64. I liked that sometimes hitting all the buttons would do a cool teleport move with the snowman. *ahem*. Next up...
Bloody Roar was when I started to understand that there was a whole genre of games that were awesome. And, ya know, turning into savage animals to tear each other apart was awesome.
Tekken 4. That was the first game that I really played like a Fighting Game. I had other people I competed with, I tried to get better, I learned the character best I could, and improved. So, for "first fighting game experience", in the experiencing a fighting game and not simply playing a game that happened to be a fighter sense, the first was probably Tekken 4.
I've of course played various other games (DOA, Virtua Fighter, some Beat-em-ups), but I don't think explaining them would have been necessary. This has already been too long winded. And if you care, the second Fighting Game Experience I had, in the above sense, was Street Fighter Alpha Anthology.