I was just about to come in a recommend Tatsunoko vs Capcom, but I see I was beaten to the punch. Very easy to get into, but also has a good deal of depth to it. It's a great choice for beginners.
Another I'd recommend is Vampire Savior. The combos are mostly extremely easy, short, but rewarding. The combos aren't the focus at all, which allows people to jump in easily - what is the focus is the neutral game. This game is all about opening people up, applying pressure, setting up traps, mix-ups, etc. The only negative I have with the game is the way Guard Teching is done, other than that I consider it to be a perfect fighting game.
It's hard for me to recommend many Neo Geo games, as they all feel like they were made with the hardcore gamer in mind, but if he's somewhat familiar with Capcom games then Garou: Mark of the Wolves is probably the best one to start off with. Other than that, I suppose Samurai Shodown has less execution requirements as combos were again not the focus.
I really feel like any game that doesn't focus on combos is the best thing to start someone off with. It means the player will not focus on combos and will instead focus on everything else - which is what is really important in a fighting game.