I love Small World, it's like Risk, but more fair and fun.
In Risk, you're constantly looking to knockout opponents and generally playing until one player has dominated and the others are asleep or for the short version, you stop after someone has Australia.
Risk: Legacy actually removes this issue. Well, sort of. The thing with Risk: Legacy is that it starts off like regular Risk (except that you vie for 4 victory points instead of utterly wiping out everyone else, though that works too). Each game that you play permanently changes the landscape. As play progresses, you eventually even change the rules. If you have a core group of players, then you can even purposefully jack with the board to benefit you in the future.
So, the Australia rule? It could be nullified by someone lowering the reward from 2 to 1. Of course, it's possible that the Australia reward could be bumped up to make it even stronger. There are other ways to make regions more appealing than just the continent bonus, though. It's a fun twist on a classic game. It's still Risk, though, and if the 3 dice vs 2 dice mechanic pisses you off, then this game isn't for you. If you hated Risk because the way to win was to take Australia and wipe everyone out, then you should give this a try, as this isn't always a viable strategy (though it's still a strong strategy early on). Make no mistake, though: This game can still be swingy.
Small World is a very fun game. It's very swingy, which means that players need to keep an eye on runaway victories. I just played a game last week where I could see how one guy was raking in the points, but we were too busy fighting each other to put him in his place. Kingmaking is a distinct possibility, but I think that's true of any army game.
If you want something less fantastical than Small World, you could seek out its precursor, Vinci. It's a little trickier to play since it's more icon-based, but once you get past that, it should be fine.
And of course, there's always Axis & Allies. I'm not a diehard A&A player, but it seems to me that one problem with this game is that each country has in ideal starting strategy. If you don't follow that strategy but your opponents follow theirs, then you get trounced. That's just my observation, part of it stems from how I usually don't like playing the formula and end up getting crippled. Maybe I just suck at A&A.
I like Advanced Civilization, but that's not really a war game. It happens to have war in it, and it usually punishes people who get too aggressive.