Melee is all muscle memory as well. Except you don't even really need to know how the game works to pick it up reasonably fast.
SSF4 is a game you cannot pick up really quickly. Not only do you need muscle memory to be good at SSF4, you have to actually know wtf is going on. You're also really underestimating how difficult it is to learn how to space in SSF4. Spacing in SSF4 is MUCH more technical than spacing in Smash by far.
Furthermore on a basis of how many buttons you need to hit, you need to hit FAR more buttons in SSF4 than you do in Melee.
Melee's not necessarily hard either, lol. More difficult than Brawl in a lot of ways, and challenging enough to be legitimately competitive, but, as you said, it's muscle memory. After that, it's a matter of recognizing patterns (reads) and spacing.
Not really true regarding the "easy to pick up" aspect of melee either. In either game, one who understands DI, crouch cancelling, sweetspotting, and has superior general techskill will win...usually decisively. Same with SSF4 and footsies, links, and option selecting. Both have ENOUGH depth to give the player who has put more time into the game a significant advantage. But yea, as far as buttons go and depth in spacing...yeah SSF4 > Melee.
However, a
truly difficult game to master would be something like starcraft or MvC2. Games where committing time and watching a few vids won't be enough.
Full post was too long and douchie sounding, so my opinion ends hereeeee.