Interesting characters with unique fighting styles. Nobody likes flat, uninteresting characters, which is why I think the VF series isn't popular even though it's the most technically sound 3-D fighter. I honestly dislike the Tekken fighting system (only because I think "juggling" is a stupid concept in modern, especially 3-D gaming; it exists in other fighting games but none nearly so much as Tekken) but I love Tekken's characters. They are half the attraction imo.
An intense combat system, i.e something that can be both fast AND thoughtful at once, and effectively separates newbies from veterans.
Variety: many different characters, many different stages, many different moves, many everything is generally good as long as you keep ONE CRUCIAL thing in mind
Balance. Easily the hardest thing for any game to do is to be able to see the metagame and balance it accordingly. When you've got 20+ different characters with 20+ different styles it's a near impossible kind of task. When a game is broken, nobody wants to play it.
Below that I guess is how pretty it looks, how many players you can have, etc., but I think that's the major stuff right there.