Chess, absolutely. My father taught me chess when I was around 4 and have been playing on and off ever since. I've learned so much from chess and owe a lot to it. For example, chess is one of the greatest teachers of strategy. It also clearly delineates strategy from tactics. Chess teaches you how to think in abstract terms and plan ahead and it teaches you how to formulate and spot patterns. It's also a superb decision making 'simulator' and it teaches you how to make sacrifices (something that children tend to learn late in life), how to value things and how to trade things.
Chess is probably the best game that exudes all of these characteristics.
And bets of all, it takes a day to learn and a lifetime to master... so you will never get bored.