Tactical turn based battles linked by RPG elements? The genre is often named "tactical RPG", and I'm a big fan of them too :)

Here on GOG, apart from braveland and king's bounty, you have
* Expedition Conquistadors : Recruit an expedition to the new world and explore the Aztec empire. Lots of exploration, some challenging battles, lots of RPG stuff (nice story, soldiers with their own peronality, leveling your troops, negociating with the locals) and a nice "party management" minigame (although it can be repetitive, but keeping your party healthy and fed can be a challenge). And once you left the linear tutorial island, you're pretty free to do as you choose, which is nice.

* Banner Saga : It's the end of the world, and you have to lead a viking clan to safety... if any still exists. Good but depressing story, the tactical part can be unintuitive (but I liked it), colorful characters, gorgeous graphics, "choose your own adventure" moral choices that can get your soldiers killed. The empty battlefields of the first game are a little bland, though.

* Blackguards : A band of rogues and renegades in the Dark Eye world. Few characters (only 4-5 of them in your party), very linear, but complex and VERY challenging tactical game. Every time I thought I mastered the tactical part, something happened to force me to change my strategy. Loved the interactive battlefields (there are often elements on the map that will allow you to win the battle, if you use them in the right way), but not a fan of the grimdark story. My advice : play as an archer/rogue, you'll thank me later in the campaign.

* Legend of Eisenwald : Play an exiled german lord in his/her quest for revenge in the black forest. Big maps with lots of things to do, some "conquer bases and build troops" but not much (you will play with only one troop, and keeping your experienced soldiers alive is far more important than a steady stream of reinforcement), a very gray/macchiavellian world with moral choices that WILL come back to bite you in the ass. The tactical wargame is pretty easy, though, but you can seriously screw yourself over in the rest of the game. I liked the game, and the whole "gray on gray" story is cool, although the generic soldiers are not my liking (for tactical RPGs, I prefer that every one of my soldiers is a unique character, rather than just a class)

For tactics, I prefer Conquistador and Blackguard, since both games are challenging and force you to really use the battlefield to your advantage.
For the story, Conquistador and Eisenwald are pretty much open worlds, while Banner is more a "linear with branching path" story. ALthough there are sidequests and a map, I found Blackguard to be the more linear of the lot, you don't really get to make any choice.

My recommandation : Conquistador. Although all of them are cool games in their own way.