The first one was Hammer of the Scots by Columbia Games. We ended up playing it three times as we tried to figure out how the Scots are supposed to win. I recommend playing with the optional rules to help the Scots in the Braveheart scenario - they need it.
I had never tried a game like this. It uses blocks instead of flat counters. This is amazingly effective because it accomplishes three things. First, it allows you to provide up to 4 'steps' for each unit, whereas normal counters provide a maximum of 2 (or additional book keeping on your part). Second, it provides a fog of war element in that your enemy cannot see your units. Third, it lets you play outside, even if it's windy.
The second game we tried was Blue vs. Gray, by GMT games, which has long had a good reputation for solid wargames. This game is mostly card driven, although there is map and a few counters. Definitely fun and relatively quick.
The last game we tried was 3-player Risk - The Lord of the Rings, Trilogy Edition. This game takes the simple dice system from classic Risk, changes the map considerably and adds a few new elements, such as leaders and quests, that make the game interesting enough to be enjoyable in a beer and pretzels sort of way. Also, there are a finite number of turns, so you can avoid all night gaming sessions.