A good fighting game makes a novice player feel powerful and an expert player feels unbeatable. No way should a player just be able to button mash and beat a real player. Plus, it needs balance. No overpowered characters. Every character should have moves that are unique but every character should have a move that can counter. Only exception should be the (often unplayable) bosses.
Visual flair is a must, too.