The Battle for Wesnoth is a scenario-based fantasy wargame. You pick a campaign to play, and your units and characters progress from battle to battle, gaining experience and telling a story along the way.
Definitely more of a focus on the war-game than the story, but it's interesting and a bit like Fire Emblem. You can set a high difficulty, but also save and reload as much as you like.
It's open source , you can download for free and create your own maps/scenarios . There is a 20-year development history, though I only heard about it 2 years ago. Had lots of fun playing through with occasional reloads.. OK in a few places I reloaded a lot :)
