IMO, the best fighting games have easy to understand, but incredibly hard to master mechanics, that allow for matches that are never the same as another. Mastering all of the mechanics is not what makes you a competitive player though, because that's a very demanding order.
This is why Smash, Tekken, and Dissidia: Final Fantasy (not solely a fighting game, though I count it. Shame it never had online play) are my three favourite fighters (and PS-All Stars being an honourable mention, as I had a hell of a time with the online mode. Thinking about it makes me so excited for Smash 4, as it will be even better, provided the netcode is fine).
Making a fighting game that demands too much time to play at a competitive level is bad game design, because gamers only are willing to spend so much time with one game. If a player feels they can't enjoy a game because they consistently can't win matches in singleplayer or in competitive multiplayer, all because they can't learn quarter-circle clockwise punch kick magic series special at X frame punch-kick 360 degree rotation anti-clockwise x5 in 0.6 seconds and push all 4 face buttons simultaneously at Y frame - they are likely going to drop the game before long.
A lot of tournament nuts tend to throw around the "JUST SPEND MORE TIME TRAINING" card around a lot, but the simple fact of the matter is that nobody should have to spend 50 hours training ALONE in a MULTIPLAYER-FOCUSED game, just so they can get some enjoyment out of it. The game should be simple enough to remember most techniques after a long period of time without playing. Because nobody can stick with a game for years upon years with complete consistency, as we all have lives and responsibilities, as well as other games we may want to play, and other activities to engage in. And of course, a game should be simple enough so that when a friend of mine comes over who has never played this snazzy new fighting game I bought, they should be able to enjoy watching their character perform cool maneuvers even with the basic mechanics and feel they are having a fun time fighting me, even if I know the game inside out.
Though honestly, this tangent is off-topic.