Inspired by DarKaoZ, here's my dream KOF tutorial:
Part 1: How to move and defend
(Covers basics of 2D fighter movement, running and back-dash, different jumps and hops, rolling, recovery rolls and GCAB/CD.)
Part 2: How to attack
(Covers normals, CDs, throws, command normals, specials, command throws, EX specials, DMs, EX DMs, NeoMaxes, Drive Cancels, HD mode and Max Cancels. Phew.)
Part 3: Defensive Strategy
(Covers using pokes for defense, dealing with basic mix-ups, dealing with more advanced mix-ups, avoiding guard crush, and using the invincibility of EX moves to avoid attacks)
Part 4: Offensive Strategy
(Covers safe vs. unsafe moves, basic blockstrings, move properties [overheads], basic mix-ups, building gauge, and taunts.)
Each section would consist of a number of easy-to-moderate challenges teaching the player about the game. The sections can be done in any order (so experienced players can skip through some of the basics), but completing them all gets you a gold star (or something equally valuable). SNKP has already had challenges like these in their games, but they've always been mixed in with the more general challenge mode. The idea of this mode would be to make players aware of what they're learning.
The tutorial characters are Kyo, Iori and Ash, since their move sets cover just about all KOF basics. Each section would be taught by one of the "master" characters: Kim (attacking), Takuma (offense), and Chin (defense). Maybe Rose or someone could handle movement? Final exam is Kyo/Iori/Ash vs. Kim/Takuma/Chin on moderate difficulty.