Battle for Wesnoth is a free turn-based strategy game, set in a Tolkienesque world of elves, orcs, trolls and dwarves.
The core idea is a familiar one. You'll start with a single leader and just a little gold, but then gradually create an army, turning raw recruits into battle-hardened veterans capable of dealing with any opponent.
The program comes with more than enough campaigns to hold your interest, though, each with their own storyline. As a beginner you might start off with something short, perhaps where you just have to find a person, maybe fight a small battle; more complex campaigns might give you the responsibility to protect your homeland against a defending army; and the longest will lead you through 20 or more scenarios, covering every aspect of the game and seriously testing your strategic skills.
If that's still not enough, there are plenty of user-created campaigns that you can download and try, or you can go to work with its map editor and programming language and build new scenarios of their own. And of course there's always the multi-player option, which allows you to challenge up to 8 friends for battlefield supremacy.