Fighting Games in General.

Good Gameplay, it don't has to be perfectly balanced, but should be fun to play.
A big roster up to 40 Chars (Including Bosses and Alternate versions)
Characterinteractions like special pre fight intros.
Good Music
Interesting stages
No "I seek Revenge for my dead whatever" Story.
Unlockable Characters and Game Modes.
No "Progamer only" requirements for Unlockable content, every player should be able to use or see everything content the game has to offer.

3D only
plenty of Unlockable costumes.

Optional:
If possible a Character Creator like in Mortal Kombat Armageddon, it's maybe not the best game but the Character creation in this game was just great.