Axis and Allies is the best board game I've ever played. It takes a long time, but it's completely worth it.
You might also try some of the Steve Jackson games. I've had a lot of fun with Ninja Burger.
Alternatively, you could play a game of Risktego, in which you play a full game of Risk, except that instead of rolling the dice to decide battles, for each individual pairing of two little men, you play a full game of Stratego.