I have to say I didn't really follow the fighting game genre much after my SNES days, my main problem is that if you look at Killer Instinct and Street Fighter II, you pretty much had to learn about 4 moves and you knew everything, everything else came down to timing and strategy, and knowing what move suits what situation. There might be a dozen characters with all different moves, but it mostly came down to Down, Forward, Punch - Down, Away Kick - and charging either Back or Down followed by Forward or Up with Punch or kick.
At no point did I have to learn that D,D,F, Y was one fireball and D,D,B, X was the other one, and then every character with a projectile has a different move set.
With the older games, without knowing the game or characters, if you knew SF basics, you could quickly do a fireball motion and if nothing happened, you knew that character had back/forward charge special moves.
A 'random fatality' input would be nice for those who can't remember 50 different strings of inputs and don't want to play with a moves list on their lap. something like D,D,Y on all characters would give you a finisher, but you need to do the real move if you want to choose one, that'd be a nice fix.