Wait until you check out the expansions. They add more to the game. Although we find that we play Just Settlers as often as we play Settlers with Expansions.
I was a big fan of Avalon Hill in the 80s, in particular Squad Leader -- odd that hasn't come up yet, I guess there aren't too many "grognards" on HTF?
Other easier AH games I really enjoyed were Dune, Kremlin, Titan, and History of the World. History is still available (slightly revised) from Hasbro, who took over the AH name, and I highly recommend it for anyone who likes Risk but thinks it a bit too straightforward. (Hasbro also has "advanced" Risk, Risk 2210 or something similar, which I've never played myself but looks fairly interesting.)
Kremlin was a hilarious piss-take on Soviet politics, imagine a game where the object is to "control" the Party Chairman and successfully "wave" at the annual parade for 3 years...
Another AH favourite was Republic of Rome, but that took some serious time. Anyone know of any PBEM games out there? No doubt Diplomacy is being played by email today, but I never played it, don't own a copy and it seems a bit late to get into it now.
BTW Lew, you're thinking of Kingmaker (War of the Roses). Never played it, but read plenty about it in the General.