This is a pretty big question, since there are lots of games with turn-based strategy
elements that aren't the same kind of game at all. In some cases, the actual fun is meant to come from something else besides the actual strategic decision-making-- say, the moving through storyline in an RPG, simulating something the player is interested in for wargames, or the feeling of exponential growth when playing a 4x on lower difficulty levels-- and the strategic elements are there primarily to provide structure and pacing. In others, the strategic elements are central. And, a lot of the time, especially when the
teleological structure of the game is complex (or just poorly defined), the design attempts to bring in fun in multiple ways, sometimes to its advantage, and other times to its detriment.
As for what makes strategic gameplay interesting when it are present for its own sake, I believe the fun lies in the presence of interesting decisions-- where
interesting means something like "meaningful, non-trivial, solvable, but not obviously calculable (by a human)". The kind of thinking called for by an interesting decision should be the same kind of thinking that the chess master Richard Réti had in mind when he explained that, contrary to the layperson's image of a chess master's thought process, he did not calculate any number of moves ahead. In our age, we have computers that play chess somewhat in the way Réti's layperson envisioned, calculating their way through a tree structure of possible moves and countermoves in search of the optimal outcome-- though even these must rely on more than brute force, due to the amount of computation required. But a human, though they may run through the possibilities in a limited scenario, does not generally play in this way. Instead, the human looks at the board and
sees strong and weak moves; possibilities
feel good or bad.
It is important, in my view, that a strategy game be designed around this sort of thinking, because a calculable problem, if a lot of attention is drawn to it, is ultimately worse for the game than a trivial one. A trivial problem is solved and moved past; a calculable one, however, presents the player with a dilemma-- either they do the work (perhaps with the aid of a spreadsheet program) and solve for the best play, spending their time on a purely mechanistic task that then leaves them with a decision that is now trivial-- or they decline to do so, and assess the possibilities in a way that is less taxing but leaves them with the lasting (and true) impression that they are not doing as well as they could be. For outcome-oriented players, games that rely heavily on decisions where the optimal play is calculable are ultimately not strategy games at all, because the outcome is determined not by the player's thinking but by their
patience, as manifested by how much of the work of calculating outcomes they're willing to do.
The tricky part is creating impactful decisions that are not human-calculable but still human-solvable-- that is, that the decision is not only
not made through brute force, but also
is made by another way of thinking that amounts to more than just guessing. There are a lot of tools you can employ to help with this problem, both mechanical (e.g. computational complexity, random elements) and otherwise (for instance, using your game's theme to make game piece properties and relationships clearer), but there is, as far as I know, no substitute for testing and tweaking things until they feel balanced. The last part of finding the "fun" is thus, by necessity, left as an exercise for the reader.