I didn't include any 3D fighters (except for SSFIV) because a) I don't have a lot of time invested in any and bK. 2D seems better to me for both learning and tournament playing. So feel free to give recommednations for 3D games if you think they fit.
I started this post as a fairly bare-bones outline, but as a I got typing this seemed to turn into a very rough draft of the actual guide
Level 1: Learning the Basics
Street Fighter II: The World Warrior – raw and polished – less complex then the predecessors, but a very solid system of rock/paper/scissors type thinking and a slow enough pace to get beginners to really think about their moves.
Street Fighter Alpha 2 – this is still one of my personal favorites as it has a solid roster without being too overwhelming and has a polished, but approachable fighting system. Probably a bit more forgiving than Street Fighter II.
Level 2: Intermediate
Super Street Fighter IV – To me, it seems like Super Street Fighter IV is a good, logical step from SF2 and SFA2. It’s a very well-rounded and mainstream game with a good selection of characters and an excellent learning curve. It’s a good game for people that are starting in the genre to really mature and grow into a game that is being used at tournaments.
King of Fighters ’97 or ’98 – seems like a good place to jump into the SNK world. A good way to jump into a game with a large roster and the team-based feature. ’97 and ’98 are probably the most classic and easiest to track down of the series.
Fatal Fury: Mark of the Wolves – is kinda SNK’s counterpart to Street Fighter 3 (see below) but not quite as intimidating. It does have some nice characteristics that will bring a fighting fan out of their beginner stages.
Level 3: Advanced
Street Fighter 3: Third Strike – one of my absolute favorites, but it often requires a bit more patience and discipline on the defense end to really succeed. It’s an excellent tournament game and is quite satisfying to play once you are used to it.
Samurai Shodown 2 or The Last Blade 2 – Seems like it would be good to transition to weapons fighters here and also learn the different pacing that these games often require.
Weaponlord – I have yet to actually play this one myself, but Ack talks about it all the time and it seems like a good fit for the “Advanced” category even though it is far from mainstream.
Bonus: Fun & Quirky
X-Men vs. Street Fighter or Marvel vs Capcom – personally, I really like X-Men vs Street Fighter quite a bit still as it isn’t too complex and has a nice balance of characters. Some may argue for just going ahead and going for the original Marvel vs. Capcom. Moving up to Marvel vs Capcom 2 will probably be a bit intimidating for newbies (although, against the CPU or an unskilled opponent, you can accomplish a lot by just mashing buttons)
Waku Waku 7 – a good Hidden Gem that I think everyone would have a ball with. Can anyone think of a better example?
