I think your complaint about computer/video games is not really about computer/video games themselves but about the weak state of AI. The reason the games play like puzzles a little bit is because of the limitations of AI. We would make the same complaint of a game like Puerto Rico if the opponents you played used exactly the same strategy every single game. After a while you'd figure out the effective counter-strategy and win every time. Would we conclude that Puerto Rico isn't a good game because of this? No, it would mean that you're not playing good players. There's nothing intrinsically different about strategy computer games: they have rules and pieces to move around and actions to take. It is taking a long time, though, for the AI to catch up and be able to present a challenge to human players.
An excellent point.
Although I labeled some game as "puzzles", let's not denigrate that term. A puzzle like "The Sims", with no clear solution and continued juggling is possible only with computers and is brilliant.
Puzzles can keep you happy your whole life, even if you find yourself mastering their form. Consider crossword puzzles.
Puzzles require strategy and tactics, just like games. The difference is that a particular puzzle can be solved in a practically short amount of time, i.e. less than a lifetime. Once you learn good strategies to solve one instance of a type of puzzle, the same strategies will apply to other instances of the same type of puzzle. The particular types of tactics will also generally apply, with experience guiding how and when to use these tactics.
Let's break down the computer game into its puzzle and non-puzzle parts. This time, we will be careful to distinguish between what is really a puzzle, what appears to be a puzzle because the AI isn't any good, and what is really a game.
Myst is an example of a pure puzzle game. Once you have solved Myst, it is solved. That makes it a puzzle.
RTT (real time tactics, which include your classic shoot 'em games) games are not puzzles, but games. However, when playing single-player with poor AI, they become puzzles. As a comparable but not identical example, Tic-Tac-Toe is a "game", but everyone knows that the game is solved. The act of playing a solved game such as Tic-Tac-Toe is not gaming. It is an exercise in memory, if anything.
On the other hand, playing a RTT game with good AI, or against another player, is a game. It has all of the benefits that computer games offer vs board games (slick graphics, heavy calculations handled by the computer, no physical presence, ...) and all of the negatives that computer games suffer vs board games (requires expensive equipment and software, limited rules changes, no physical presence, lack of social gaming etiquette or out-of-game socializing, ...).
RTS (real time strategy, which includes civ building games) games are both puzzles and games. If you separate out the strategy part of the game from the tactics part of the game, i.e. the resource building versus the battles in Civilization, you separate out what I would call the puzzle aspect from the strategy aspect.
In other words, the current definitions consider "strategy" the resource building and acquisition, and "tactics" the fighting the battles. In contrast, my definitions consider the resource building and acquisition the "puzzle", and fighting both "strategy" and "tactics".
The building part of the game takes place entirely removed from any other player or even AI opposition. The initial map may change, but thereafter you are not playing against anyone. There is then the right way to do things and many wrong ways to do things. By round X, you have to have the most A, B, and C.
OK, I'm not being entirely fair. Which of A, B, and C you want to have the most of depends on your strategy going into the next part of the game, the combat part. So, yes, strategy comes into play IF AND ONLY IF a single correct strategy cannot net you the most of ALL of A, B, and C. If it can, you either do it right, or you don't. That's a puzzle, not a game.
The same pejorative use of the word puzzle has been used against any number of board games that have such minimal player interaction as to bear such comparisons. But even these board games have some interaction. Imagine a board game where you played a dozen turns completely without any interaction at all, and only then intersected with the other players. (Games that seem like they should do this, like Diplomacy, Civilization (the board game), and so on, don't.)
Once the fighting kicks in, you are back to "game mode". Despite the game now being in what is called the "tactics" phase, there are still major elements of both strategy and tactics in games like Red Alert, Civilization and all those other combat games.
Of course, it would be nice if there were other ways to interact in competition without having to resort to combat. Wouldn't it? I welcome any suggestions for computer games that involve resource building followed by something other than combat.
In the meantime, if you like full-time intense strategy and tactics, and you don't want to spend lots of money or sit in front of your computer all day long, and you want to actually gain more than strategy and tactics skills, but also social skills and manners, go play good board games.
Bonus Link: a kick-ass article about the relative value of roleplaying vs traditional games.