Short answer: Increase the number of variables.
Why? Chess was "easy" for a computer to beat because there are only a certain number of pieces and possible moves. Go was "harder" because there were more possible moves. A game that is even harder for a computer will have even more possible moves.
Example: Strategy games. I have yet to play an RTS* where the computer can win against an experienced human without cheating. Why? The number of variables. Resources, the effects of resources over time (do you use them to get more resources, do research, or produce units?), how scouting and intelligence is handled, and how the plethora of available units are managed. You could probably tell a computer how to "kite" long range units, but telling it when to kite, for how long, when to make those units, etc. etc. with the combination of every other unit and its possible uses would be nearly impossible.
Asking a computer to simulate every possible move in chess and the response that is guaranteed to win against that move is trivial with today's computers. Asking a computer to simulate every possible click in an RTS with resources, research trees, and complex unit types is likely impossible. Yet even inexperienced humans can master the basic elements of these games with relative ease compared to the computer programming necessary.
*I know I am using RTSs as an example but any RTS can theoretically be made into a very similar turn-based strategy game.
Another thought: you could also pick a task that humans already find easy but that is actually very complex, like folding laundry, and make that into a turn-based game. Players could take turns folding a piece of clothing -- every turn is one piece of clothing -- and the player who has taken the least amount of time to complete 5 turns wins.
We find this simple because we have a conception of what words like "up" and "inside-out" mean -- take a shirt, make sure it's "right side in," lay it "flat on the table" so the "collar" is "away from you," take the "sleeve..." etc. etc. As a human, you know what all the phrases/words in quotes mean; essentially, you have simplified a basically infinite number of variables into instructions that take only a few words. Explaining that to a computer is more or less impossible. And even if you explain it for one shirt, will the computer know every shirt? Long sleeve? Short sleeve? Button up? What if the collar is popped? etc.