There's some really good wargame suggestions here.
I also suggest trying some miniatures wargames. Now, you do NOT need miniatures to play. A 1 x 2" rectangle of cardstock labeled "Sherman" and with an arrow pointing along the long axis is now a Sherman tank. A penny is a half squad of infantry, a nickel is a light machine gun, a dime is a heavy machine gun, a quarter is a mortar.
Books and blankets and stuff can be terrain, or put brown paper on the table and draw terrain.
In the medieval period you can use 1 x 1 squares for foot and 1 x 2 rectangles for horse. An arrow indicates front, and label them.
I recommend miniatures because you can get a wider variety of scenarios. The straight "meeting engagement" between two roughly equal size forces is the single least interesting form of battle. A small force trying to hold a choke point against a larger force will teach you a lot about the importance of terrain, sight lines, movement rates, etc. It's a little easier for new players to get a "gut feel" for what's happening with miniatures, in my experience.
For rules for the medieval period, Terence Wise's book "Medieval Warfare" is not only a nice intro to the 14th and 15th century, it includes a simple but eminently workable rule set. Or, you can download the old Heritage Models' "God's Acre" rules here free:
http://www.wargames.co.uk/Rules/GodsAcre.htmI'd recommend "CHAINMAIL," but they're so fucking expensive nowadays I can't in good conscience.
For WW2, the old WRG ww2 rules are available, again for FREE (See how your old Uncle Gronan takes care of you?)
http://www.wrg.me.uk/WRG.net/History/OLDWRG/WWII.pdfThey again are eminently playable and reasonably good for the period without being nightmarishly complex.
TRACTICS and FAST RULES, like CHAINMAIL, have been priced into the "collector's market."
If you can find the old RAFM "Universal Soldier" rules of the late 70s they're pretty good too. They are VERY based on CHAINMAIL 1:20, but they added the idea of seperate attack and defense class; so 13th Century knights are Attack A, Defense B, representing their heavy mail armor, while late 14th and 15th century knights in full plate are Attack A Defense A.