I apologize beforehand for the book I have written. I got carried away. I just hope it gives you some good ideas.
What you are describing seems to be a fundamental shift in the way you view and play the game, and I think the clue in making games that avoid it, is in trying to understand the shift, so I'm hoping to explain it in this post.
And that fundamental shift is going from solving problems to executing solutions.
When you start a game, it is completely new. Your understanding of how it works is likely limited to maybe some reviews, a trailer, or perhaps a "what is X?" video.
At this point; everything you see is a problem and everything you try is new. Even the simple question of "I wonder what happens when I click 'new game'?" can have surprising answers. It might jump into a movie, or a character generation screen, a tutorial, or straight into the game. Whichever it is, you're going to have to figure it out as it happens and it is almost certainly going to present new problems to solve. (Such as "How do I get started?" and "How do I win?")
As you become better at a game, you start gathering more and more answers to problems. At some point you know that when starting the game, you need to collect X resource and find Y person and build Z building. But new questions will start coming up; more advanced ones that you could not even have attempted to answer before. "How do I beat the Hard AI?" or "How can I beat this level?" are questions that are only of interest to a good player, but they still put you in problem solving mode; you simply don't know yet how to do it, but you're going to try and come up with some possible answers and try them out, and see if any of them work.
And in doing so, you'll learn some new things about the game. New experiences will be had, and you'll gather more knowledge which you can use to solve even harder problems. (like "How do I beat the Extreme AI?" ;) )
But at some point, for some parts of the game, problems stop requiring you to solve them. You already know the best solution. What you need to learn or do, is to execute those solution to the best of your abilities.
For example, in a platformer, the first time you find a ravine that you need to jump over, it's a problem you need to solve. Can I jump far enough? Do I need a powerup? Do I need a running jump? These are problems to solve. But when you get to level 10, the "jump this ravine" problem has been solved. You know exactly how far you jump, how much of a running start you need. But this ravine is big. And the landing point is small. And if you want to make it, you need to time your jump just right, or you'll fall in.
This is executing a known solution, which can also be challenging in its own right, but is a completely different type of skill to work on.
In all your examples, you are describing the move from solving problems to executing solutions. When you know exactly which hero to pick, or which tech to research, or how to keep your people happy, all that remains is to perfect the execution. Can you reach a higher score? Can you beat a better opponent? You don't need to solve any complex problems; you mostly need to learn how to build faster or aim better.
But how do we fix that?
So you're asking for design methods to fix the shift from solving to executing. In order to be stuck in solving mode, what you need is a problem with no clear-cut solution. And, ideally, if you want to make this work for competitive games, a problem that can't be perfectly solved at all.
A big one for single-player games that want to stay fresh for a long time, is procedural generation. The fact that your levels are randomly created means that all of them start with problem solving: "where am I?", "what here can I use?", "what do I need to be on the lookout for?"
Procedural generation will work you keep you in solving mode, until you intuitively figure out the restrictions on the generator and start expecting things. "Okay, the game gives me a two minute grace-period to set up. Also, there has to be a box with some weapon nearby. Let's go."
So, the best way to keep players on their toes, is to make the pattern as broad as possible. But that will play into the second point, also.
Another one that helps a game stay fresh, is to have multiple paths to victory. Civilization has a set of different victory conditions (tech, diplomacy, conquest, etc) and each requires a different way to play. In addition, defending against each also takes a different approach. This means that a game where a strong player is going to win a diplomatic victory will go very different from one where a strong player is going to win through conquest.
This, in turn, means that while you can have a good idea what you will do in your rush to win, you won't know what you're going to defend against, and that will keep games different. At least, assuming that you actively need to prevent other players from winning and there isn't one fixed method to do so, which sadly in Civ is not the case usually.
You can get pretty extreme with this approach, too. In civilization, most races are roughly the same. But for example in Endless Legend, some races get traits like "You cannot be at peace with anyone" or "You can ban other players from trading resources at will", which force you to try even more things.
Multi-strategy games will work until the player figures out a 'certain win' strategy, or until they have tried all possible strategies. (In the latter case; congratulation game designer, you won.)
You can also keep a game fresh by doing away with limitations and letting players go completely wild. This is a fairly new phenomenon that has been made wildly popular by (of course) Minecraft. I'm not sure what the creators thought people would build in the game, but I'm fairly sure that "A working processor" or "All of Minas Tirith" weren't it. But there you have it.
Limitless games will keep you in problem solving mode until you get bored of something else in the game, so really they are the perfect thing you're looking for. Of course, at some point, you are no longer "playing a game", but are just rebuilding a different hobby inside a piece of software that was once a game.
Another issue with these games is often that they lack a clear goal. Goals can drive players towards something and keep them coming back, but not everyone sets their own goals. And it's very hard to set goals in a game that can go anywhere.
Another approach is games that change as you play them more. This type of game on its own seems to be very rare, but you can often see it implemented by continuous developer attention.
For example; collectible card games that have new cards released, MMOs with expansions, DLC in strategy games, balance tweaks, etc. These are always a delicate balance between keeping the metagame moving enough that it keeps people interested but not moving it so much that is makes investing in the game seem pointless.
Games that do this intuitively would be awesome, but it might be future music for now. Game design and balance remains an art for now, and computers are not very good at art.
Many of the above options can be combined for greater effect. I'm going to hypothesize a game based on the 4X principle (like Civilization) that tries to go for maximum "problem solving mode". (But it will take huge developer involvement to run it, I think. So it might not actually be a very good game.) We'll make this an MMO game, because those are by far the hardest to do this way, due to all the players getting together to write down solutions.
First up; take a working chassis for a 4X game. Some setting, some tech, buildings, unit types, victory conditions, etc.
Since this is an MMO type game, we don't expect players to be logged in constantly and the runtime will be fairly high; let's say one month. When you are absent, your AI advisor will play for you. (There's some games in the market like this)
Now, we create a procedural world. This is common practice for these games, but we'll take it a small step further: while we strive to keep the game balanced, we make no attempt to allow all types of victory conditions and all strategies possible from each starting location. Start without iron? You'll have a hard time fielding a strong military; might want to rethink that conquest victory. Stuck on island? Guess expansion isn't for you. We want the start position to be fair towards "Can this player reasonably win?", not towards "Can this player reasonably play a fixed strategy?"
Then, to make it even harder to have a fixed strategy before game start, we'll vary (but make it known) how hard each type of victory is on this map. Maybe this time around, conquest is made easier, but technology is more expensive. This means that the "best strategy" from the previous game is now useless if it can't bridge the gap created by your completely different starting position and the different relative complexity of the win condition. But if you understand the game well, this just means that you have been given a hard problem to solve; which is exactly what we want.
(Note that it's not automatically true that everyone will aim for the easiest objective. Since we know the relative difficulty of each objective at generation, we can give a bonus to players that are in a region which is naturally geared towards a hard objective for this map. Kinda like how some games have special "2vs1" maps where the 1 player has a defensive advantage.)
Then, let's give the game a mechanic where the players can make broad changes to the rules. Civilization's World Congress had some of those, but they were a bit tame and came in late. I've played a board game where you had rules like "nobody can build more than X warships" or "if you don't protect your colonies with armies, they revert to neutral" and a bunch more, including ones targeted at players. That's more like what we need. This means you can't plan out your strategy from the start; you need to adapt to the rules of the game changing. But still, if you know the game, you'll know roughly what you can expect, so you can still get better, but the available rules for each game will vary. You can learn the game, you can be good at the game, but you can't solve the game, and so you'll never get bogged down in the "Perform X, only slightly faster this time" metagame.
At this point, I think you've got a game that won't get boring for a long time because it cannot evolve a metagame of the sort that DotA or Civilization has. It will change too much to have a fixed metagame, while also changing very little, so that you can learn to become really good at it. It just takes a completely different skill to be good: you need to be adaptive and good at solving problems, not good at executing the best strategies the fastest.