There are two features of games that have always appealed to me. First, the good ones put you in a place where you are explicitly thinking out different ways the future could play out -- the possibilities that are more or less likely given what you know (and what you don't know). Second, many of them let you drag someone else (whether your opponent or your teammate) into thinking through these situations, too.
Any game where you have to make choices about what to do involves some sort of strategy, and formulating or refining strategies is a work-out for your brain. This means that games, in general, tend to be brain-friendly giftables.
It's worth noting that many of the games which connect to qualities of mind that are useful in scientific problem-solving are fun for kids (and adults) who don't think of themselves as having any special interest in science. I'm not saying you should use such games to launch stealth operations to get kids interested in science ... but I'm not going to stop you, either.
As an added bonus, none of these games are going to shove gendered expectations down a kids' throat
That said, here are some of the games I like best:
Black Box (Parker Brothers)
I am sad to report that Black Box (which came out in the late 1970s) is currently out of print, but should you encounter it used (at a reasonable price), you'd be a fool not to snap it up, for it is one of the best hide-and-seek games ever made. Where Battleship lets you look for hidden ships one grid-cell at a time, Black Box asks you to deduce the location of hidden "targets" (plastic balls) from the ways they influence the behavior of "rays" sent into the box from various positions. The game sets out a universe in which rays can be deflected or reflected by nearby targets or, should a target be directly in the path of an oncoming ray, where a ray you've put into the box never comes back out of the box. The goal, depending on whether you're seeking or hiding, is either to correctly identify the locations of all the hidden targets by using as few rays as possible, or to stump your opponent as to where the targets are hidden.
As you play the game for a while, you start noticing that there are interesting -- some would say sneaky -- ways to compound deflections which make it harder to discern the precise arrangement of targets in the black box. This means that the player hiding the targets can come up with some fiendishly clever target configurations, and that the player seeking the targets will make more sophisticated choices about where to put in a ray in order to get the best information about what's going on inside the box.
Are there parallels here to some of the inferential reasoning scientists do? You're darned tootin'! But I'm not sure I had any awareness of that when I played this game as a kid, and it was still the Best Game Ever. This is not the easiest game to find, but if you do, you win. (Maybe you need to find two copies of the game for there to be a reasonable chance of giving one as a gift to anyone but yourself.)
There's also a play-against-the-computer version of the game online
Rat-a-Tat Cat (Gamewright)
This is a game for 2-6 players, ages 6 and up, and it came to my attention when a dear friend gave it as a gift to 6-year-old twins that we knew. What was striking was how, after the kids were down for the night, the grown-ups stayed up for hours playing Rat-a-Tat Cat. It's that kind of game.
The game is played with a deck most of whose cards have numbers from 0 to 9, although there are some "action" cards as well. Each player is dealt four cards, and the goal is to get as small a hand (in terms of the number your four cards adds up to) as possible. For the purposes of adding points, if you're left with any action cards in your hand at the end of a round, they're each worth 10. Each turn, you draw one card from the top of the deck or the top of the discard pile to try to improve your hand, and you discard one card.
There's a catch, of course: when you're dealt your four cards at the beginning of play, you leave them face down on the table, making a row of four cards right in front of you and only looking at the two cards on the ends of that row. Not only do you not get an initial peek at those two middle cards, but you don't get to look again at the cards on the ends unless you draw a "Peek" card and decide to use it to refresh your memory about one of them. You can also use a "Peek" to look at one of the cards in the middle of your row -- or at a card belonging to one of your opponents (even one that your opponent has not yet seen). But it's not like the deck is brimming with "Peek" cards, so much of the time, you draw cards and decide what to do with them based on limited information even about your own hand! Another action card of note is the "Swap" card, which lets you trade any of your cards for the card of your choice of one of your opponents. Of course, you (and your opponent) don't look at either of the cards being swapped.
Play continues until one player decides he or she has the lowest hand and says "rat-a-tat cat", after which all the other players get one more turn with which to try to optimize their hands.
This is a beautiful game for developing memory and a sense of how probabilities are influenced by the make-up of the deck. Once you're clear that the deck has many more rats (high value cards) than cats (low value cards), you can start using what you see (in your draws and in the discards) to work out good guesses about what's going on in your hand and in the hands of your opponents. If you play with kids, you may be surprised at how quickly they develop a feel for this (and thus, at the stiff competition they give you)!
Set (Set Enterprises)
If you're more of a visual or pattern- recognition person than a number person, you may prefer Set. You can play this game with two or more players, or even as a solitaire game.
The deck is shuffled and the dealer lays out twelve cards, face up. Each card has various features: shapes, numbers of those shapes, colors, and shading. The goal for each player, looking at the twelve cards spread out on the table, is to identify a "set" of three cards. If you find a set before the other players, you get to pick up that set and keep it. Then, the dealer replaces the cards you've collected and you (and your opponents) try to find another set before anyone else. If there's no set in the initial 12 card array, the dealer will add another three cards to that array. You keep going till you've run out of deck.
What makes the game a mental workout is how a "set" is defined. Three cards constitute a set if, for each of the four variable features (shape, number, color, and shading) the three cards are all the same on that variable (e.g., they all have ovals) or the three cards are all different for that variable (e.g., one card has one oval, the second card has two ovals, and the third card has three ovals). In other words, you need to check all four variables to see if you have found a set, and each of the variables must separately satisfy the rule (all three are the same on x or all three are different on x).
The standard rules reward speedy identification of sets, since you don't take turns. However, there's a penalty for claiming something is a set that turns out not to be. (All the players inspect each claimed set to make sure it fits the definition.) One could certainly set up "house rules" in which players take turns, though.
Rush Hour (Binary Arts/Thinkfun)
Rush Hour is a puzzle game, and as such lends itself nicely to solo play. In the whole time we've had it, we've never played it as a player-vs.-player competition, but rather as a group endeavor.
The game board is a grid representing a walled parking lot with just one entrance/exit. You pick a card that sets out an initial arrangement of the various cars in that parking lot. Your job is to safely navigate the red car out of the parking lot.
The catch, of course, is that you can only move the cars straight ahead or straight back relative to their initial alignment in the lot (no parallel parking or three-point-turns here), so you need to figure out the sequence of moves that will clear the path for the red car to exit. If you get truly stuck, the back of the card has the sequence.
Once you get your fill of two-dimensional spatial relations, you may also want to play:
Block by Block (Binary Arts/Thinkfun)
Block by Block is another puzzle game, so you can take turns trying to solve the challenges, or work on the challenges together, or work on the challenges all by your lonesome. The game consists of seven three-dimensional blocks of various shapes and a set of cards showing you larger three-dimensional objects to build by arranging the blocks.
As you might expect, some of the challenges are reasonably easy to figure out, and others are very, very hard. That extra dimension of wiggle adds a lot more possibilities to work through. Lucky, you have a set of blocks with which you can, physically, work through those possibilities -- and the more you do that, the easier it becomes to work through these kinds of possibilities mentally.
If you get stuck on a challenge, the back of the card offers advice on the first three blocks in the assembly. If that turns out not to be enough to get you through the challenge, further down on the back of the card you can get the detailed solution.
This is a nice game for the recovering Tetris addict in your life.
Gobblet Junior (Blue Orange)
Gobblet Junior is a game played on a three by three board, and the goal is the same as in tic-tac-toe: get three in a row of your pieces, either horizontally, vertically, or diagonally, before your opponent does the same.
The twist is that each player has six pieces, two each in three different sizes. The smallest ones can get "gobbled" by medium or large pieces -- from either player -- played on the same space, the medium ones can get gobbled by the large ones, and the large ones can't be gobbled at all. But since each player only had two large pieces, there's no way to get three in a row without being vulnerable to gobbling.
Another difference from tic-tac-toe is that you're allowed in subsequent turns to move pieces from where you initially played them. If the piece you're repositioning has gobbled another piece, the piece underneath it stays put while you reposition the piece above it. (Also, you can't reposition your own pieces that are currently gobbled by other pieces.)
This game adds an extra layer or two of strategy on your standard tic-tac-toe. But if three-by-three starts seeming too easy, you can step up to the four-by-four version in Gobblet.
Decks of cards and rules for favorite card games.
Teaching kids how to play cards sets them up for years of fun. Pair a deck or two with a cribbage board, or a book about poker, or your favorite book of rules for card games and you've got a gift that can grow with its recipient. Or, if there are favorite card games from your childhood (or your time at school, or in the pen), why not write up "recipe cards" with the instructions? Here are the rules to my family's favorite rummy game.
Playing games gives us a chance to interact with other people while making our brains happy. It doesn't get much better than that!