Make sure that single actions can have multiple different outcomes depending on how and when they are used
Strategic complexity is created when a player has multiple mutually exclusive actions* they can take which could all theoretically lead to victory, and the player has to figure out which one is the best. The more plausible options they have, the more complex the game.
The flip side is that learning complexity the number of different types of actions a player has to remember, and how many effects each action has.
The solution is to give the player fewer different actions, but to make those actions contextual. In chess, the only thing you can do with a pawn is move it forward (okay, or forward at a diagonal). But that action can be used to threaten your opponent's pieces, or defend your own, or block off movement avenues, depending on where the other pieces are on the board.
In Go, there is precisely one action a player can take. Every turn you will place one of your pieces. But there's over a hundred different places you can play your piece, and each location will affect the game differently.
Not every action has to be contextual (in particular, drawing cards is a vital part of most card games, and most of the time it's pretty much the same no matter how or when you do it.) But the majority of your actions should be capable of affecting the game in multiple ways.
Reward strategic planning, but don't penalize its lack
Nothing is worse for a new player than to get halfway through the game and realizing that none of the actions they've taken so far actually bring them closer to victory, because they failed to take some specific action earlier in the game which they didn't realize at the time was necessary to make their strategy successful.
In Settlers of Catan (possibly the most iconic gateway game), there are only four different things you can spend your resources on. Each one brings you closer to victory. Now, some are better at it then others, but even if you've spent your entire game building roads, you can get a few victory points out of it.
Obviously, you can't idiot-proof your game, and you shouldn't try. But the skill level of "I am not trying to plan at all, and instead just picking actions that look good" should lead to forward movement towards the goal.
*Sometimes the mutual exclusivity is only in the timing - you can do one and then the other, but not both that the same time. That still counts, if the timing matters.
