I have looked, but I have not been able to find a simple scenario to learn the game. I don't understand why the tutorial is the whole Korean war -- gotta learn to walk before you can run.
I'd like to start with a simple infantry v. infantry, and then gradually move up to more complex scenarios.
Well, that sounds like a good plan. And the suggestions above, Curtis, Klink, L'zard are all good starts.
I'll add -- "Read the AARs" -- even about the scenarios that are too big or not your favorite era; a good AAR will write about why and how the player tried something, and you can learn things reading about Mideast conflicts in 1990's that applies to your trying to win the St Mihiel scenario.
But you do learn by playing --
if you want WWI era, look for Balkans 12 and Balkans 13 in the Classic folder. Hint - play as the Bulgarians, it's more fun.
Look at Cherbourg (also in Classic) - play as the Allies, set the air to AS or CS and forget about them; it's a 3 yards and a cloud of dust (or rather 2.7 meters and a mouthful of bocage)
or try 1 of the first 5 Road to Moscow scenarios in WWII East Front folder. Play as the Germans, and set the air units and forget them.
For any scenario that does not state in its scenario header that is designed or written for TOAW 3.4, then I suggest setting New Supply Rules to OFF, and New Turn Order to OFF (play options, page 2 from the main menu). You could get a surprise playing an older scenario with those ON, while the basic game is still good.