That's Battle for Wesnoth! Almost guessed it earlier, but that last hint really gives it away!
Finally Ka-Pi guessed it. Yes, Battle for Wesnoth. I had to make a more specific hint, because it is time to unveil (already a few days late, but I'm catching up).
Battle for Wesnoth is a tactical round-based strategy with strong RPG-elements (not unlike Fire Emblem games). The fights happen on a hex-grid. While in Fire Emblem all fighters are given to you through the story, in Wesnoth you hire units of certain types additionally to the heroes you get with the story. Hiring units or recalling some you used in the last scenario costs you gold, so that limits the troops you can bring. Gold is earned by capturing villages, so if you do that cleverly, you can have a bigger army.
The setting is a medieval magical fantasy world. Many of the factions you can play are typical: humans with knights, mages or sometimes thieves, dwarfes, elves, orcs and so on. Merfolk on the other hand was something I don't see happen that often. Or undeads.
The game has currently 16 main campaigns. I say currently, because the game is constantly developed on. That is not all. The game has a thriving community, that develops tons of user-generated campaigns, maps or add-ons. Each campaign has it's own story, although they may be connected as all happens in the same setting.
If playing the single-player campaigns isn't enough for you, you can play online matches.
Something that is special is, that the game is an open-source game. Usually I see that OSS-games suck. While the open-source community excels at technical stuff, it often is missing artists or a general concise direction. I think the art here is good (although you could argue it is only 2D, but many of the games in my list are, so that shocks me not), the music is pretty great and the concept of the main campaigns is great.
The game can be downloaded for free from the website: http://wesnoth.org/
Wikipedia, MobyGames, OGDB, IGDB