i would start with the moveset and guarding. from what i've seen, when people start playing they have the tendency to mash because they don't know what else to do. then they just mash and never guard because they've gotten used to mashing only. reassure them that it takes time and that greatness does not come overnight, etc
Yeah teach them the basics of the movesets of any characters that interest them. Don't go into all of the moves, they won't be able to remember them all anyways and it'll just add the appearance of unnecessary complexity. Point out the general trends in the move sets, that things like 6B is generally a poke, 2B is generally low, 8B is a jumping attack, BB swings twice, etc.
I'd definitely cover blocking early on as well. The difference between high/mid/low. And show them examples of advantage/disadvantage.
Explain things like throws, unblockables, guard breaks, critical finishes (when to do one, I've seen a fair number of noobs spam that button at the wrong times), guard impacting, stuns, shaking, stepping, 8-way run, so they know the mechanics of the game. If they start getting overwhelmed, switch back to learning movesets.
I'd at some point, show them all of the different characters and have them try a variety of them to get a feel for different styles. Pick one they like and start going into the moveset more deeply, and mention things like mixups and combos with concrete examples.