It really depends on what you mean by complexity...
My personal favorite for an 'intro' wargame is L2 Design Group's
The Russian Campaign. It's a classic, operational level wargame originally published by Avalon Hill back in the 60's or 70's but L2's version is still in print.
No step loss, supply and re-enforcement rules are very simple, not very many special units, Combat is a breeze as long as you can calculate odds, (CF 18 vs. CF 9 = 2:1) and it does a good job of simulating the campaign without getting bogged down in a lot of detail.
As an old game it also uses a lot of the more traditional mechanics that make their way into more modern games.
However, a couple nits to pick.
The OB (Order of Battle) for both sides may as well be based on fiction.
The Guards units make an appearance, but there is no mention of the assault armies, no NKVD divisions ect.
The Supply rules are perhaps too simple
There are a lot of double counters... You can use NATO symbols, or pretty pictures of tanks, and of course if you're playing as the Axis there is the option of having censored counters that do away with those nasty SS symbols
... Seems a little redundant IMO.
Also keep in mind that although the rules are simple, it is still a hardcore wargame, expect to spend 40+ hours playing. The last playthrough I did we played for about 4 hours 3 Sunday's a month and it still took us almost 8 months to finish. A lot of this was due to the fact that we had to go through the setup/breakdown process every week which took about an hour total, but each turn still took 45 minutes to an hour and a half each.
However, all that aside The Russian Campaign has stood the test of time remarkably well, and if you can look past the ahistorical stuff it's a good introduction to more complex games.
Bento's suggestion is good too, GMT games produces some very consistently good games incorporating some very innovative mechanics for wargames. They're probably my favorite publisher overall though their complexity tends to range from the medium to high end. I'm very intrigued by
Blood and Sand as a possibility for a more casual 'pickup' wargame. It looks like it might your needs fairly well too, though keep in mind it isn't out yet so I can't exactly give it a real endorsement.
*edit* Another note on GMT games. If you want to give a tactical scale (commanding a single battle) a try, you can't possibly go wrong with their Musket and Pike series based on the 17th ca. Kicks off with
This Accursed Civil War and there are 3 others in the series so far. Not a beginners wargame though (though the tactical ones rarely are) so might want to hold off on it for a while.
