Recently, I've been caught up in a game called
Battle for Wesnoth, a turn-based strategy game in the likes of Civilization II (the battle parts) and Heroes of Might and Magic, but simpler and more straightforward. It is available freely over various platforms, which I first found over Ubuntu's repository (so the version I'm playing is the Linux version), and it has quite some nice campaigns to begin with. Alternatively, being an open source game, there are plenty of user-made campaigns and maps that can be downloaded.
The setting is a medieval fantasy (so you have things like orcs, elves, undead and, of course, the ubiquitous human) based loosely around a kingdom called Wesnoth. The campaigns that come with the game has several storylines running together, the most fundamental of which is Heir to the Throne. It is about some evil queen usurping the throne and killing all possible successor, but one mage loyal to the king managed to smuggle out one of her nephews (sounds so familiar, eh?).
That being said, I think I suck at turn-based strategy games. I suppose, due to the more numerical dynamics of the gameplay, it is harder to outsmart the AI (unlike in real-time strategy where you can amass a huge army to steamroller enemy forces). Nonetheless, this game has some easy campaigns which are rather fun and has some pretty intriguing storyline.
Sure, it cannot complete with games like Heroes of Might and Magic V or Command and Conquer: Generals, but for a game that is free, Wesnoth is considered rather good. If anything, it
does remind me of those older games I played when I was young... I mean, doesn't this look somewhat familiar?

Do give it a try. It doesn't really hurt if you don't find it to your taste. It's free anyway!