I would therefore caution people on two things: (1) your personal memories of early childhood are often quite distorted, and (2) it's not fair to impose upon a child today the expectations that come from your own ego-distorted memory.
This post caught my attention because I happen to be the father of a 5-year old son, and I myself have been searching for interesting mental exercises to share with him.
It's been an exercise for me as much as for him, teaching me about patience and tempered expectations.
Five years is YOUNG. A generation ago, early childhood educators in the U.S. didn't even typically introduce reading until age six. We start reading in kindergarten now, but typical 5-year olds can generally be expected to recognize repetitive words and basic arithmetic concepts (e.g. 1 + 2 = 3). Even that is limited to short periods of study in each sitting.
Children may vary, but I believe that many of the suggestions on that MathOverflow.com page (as well as comments here about chess, etc) would be better suited for around 7-8 and up. I think it would be unrealistic to expect the majority of 5-year olds to handle much of this, and it would be a mistake to push too hard at that age.