supers and meter are a reward for taking offensive initiative foo
anyway, definitely check this out:
http://skullgirls.com/2011/10/tutorials-teaching-the-untechable/yeah, people are clumsy on the joystick when they first start, but that's not that big of a barrier at all. also, your potential solution of widening the input window: consider the distinction between walk forward qcf vs. dp. it's tough to just widen the input window.
but yeah, the big issue i think is your third point. you shouldn't focus on even mechanics specific to your game. emphasize core fighting game concepts.
maybe create a tutorial where the player has to figure out what normals aren't punishable on block, for example. a lot of players when they start out hit sweep all the time. they understand that it does more damage and has a long range, but it doesn't occur to them, at least initially, that it leaves them at negative frames. teach them level 1 stuff-- stuff that they can control. eventually move on to strategies and counter-strategies that focus on situations that a given character wants to get into or avoid.