If you haven’t tried Hero Academy, I’d recommend it, simply for the research value. While the maps shake things up, the possible interactions between the teams make for the majority of gameplay. It’s human vs. human only, so game balance is extremely important. I really like how you can try many different things on your turn before you commit. Also, I like how the only randomness is in unit draws; there’s no randomness in combat.
Chess, of course, is the quintessential example of a TBS game where the mechanics are what count. 
I really enjoyed Panzer General II, III, and Pacific General, as well. Maps were a big part of why those were fun, but so were the RPG elements (gaining experience, buying new units, getting prototypes and leaders, etc.). That worked because the turn-based battles were linked in campaigns, in which you carried units from one battle to the next. Fantasy War is another example of that sort of TBS game.
Disciples II comes to mind a different kind of TBS game. It had a world strategy map, where you explored, found treasure, defended cities, built units, and started battles. That actual turn-based battles had no movement, but that very simplicity lent itself to an amazing depth of possibilities.
Heroes of Might and Magic had a strategy map layer very similar to Disciples. It’s turn-based combat system was completely different, though: you basically needed stacks of as many of the same kind of unit as possible. There were a lot of different units and abilities, which made the combat engaging.
Both Disciples and HoMM, by the way, feel like the strategy map is one big game of “whack-a-mole” (gain one city, lose another; you can’t defend everything).
King’s Bounty solves that by taking the combat of HoMM and making it based on a single party, so that you don’t need to capture and garrison cities; you just go around exploring, fighting, and getting stronger.
TBS games have lots of permutations and combinations.
Be interesting to see what you all come up with.