Here are some of my choices:
Art of Fighting 2 - The backrounds are awesome. Look at Robert's mansion backround that has a fountain and a 'vet sittin' pretty. The butler even peeks his head out of the door to catch the fight. The bass going on in that tune is sweet as well. Makes you really feel like you're fighting at a country club of some sort. Lee's stage is awesome with all the tourism going on and people stopping by to watch. His music has a very far eastern sound to it as well that goes well with his character/stage. The secret agents in all the backrounds makes it pretty cool too.
Mark of the Wolves - Just look at Gato's backround and listen to his music. Genius at work. I adore Rock's stage. It truly makes southtown come alive, and the Robert Miles excerpt really makes it seem like there's a nice party going on in the club behind. Nice cars as well. Fucking class A, man. Then there's Terry's stage, Kain's stage, Hookutomaru's music.. man, this game is just oozing with great atmosphere. I just wish it played a little different, but that's not the topic of discussion
Fatal Fury Special - "Wow SG, I didn't know you were gonna pick that!" Well take a gander upon Geese, Krauser, Terry, Cheng, Joe, Mai, Duck, and Tung's stage. That's just scratching the surface of the game! All awesome backdrops that are accompanied by equally awesome music (especially Geese and Krauser). Bright and beautiful colors make them really come alive.
Samurai Shodown 2 - This is the difinitive Samurai Shodown game for me. EVERY single one of the backrounds is A+, best Neo has ever put out. I fucking love fighting at Sieger's place - having guards and a king watch you with that music going on makes it really seem like you're fighting for your life. Galford's stage really brings you back to early America, and man does that music just KICK!! Fuck man, it just doesn't get any better than this! I could go through listing all the stages and such, but they are all awesome, and this is one of the few games I love all the characters, music, stages, sound effects, everything.