The Phantom Tollbooth is enjoyably mind-opening, if handed to a child at about the right age. It's very light-hearted, but is liable to instill thinking about thinking. I read it when I was 10, and again at 12, and again at 14, and again at 16, getting deeper appreciation each time.
Also, I suspect the Tiffany Aching books are ideal - but I'm a huge Discworld fan, ymmv.
I agree that The Phantom Tollbooth is especially useful for multiple reads. I read it when I was 8, then when I was 10, then 13, and again when I was 15. It's a wonderful example of a multi-layered children's book that adults can appreciate on an entirely different level than kids.
Also, it taught me much of the basics of good writing, in a way that primed me for reading, eg, Orwell's essays on the use and abuse of the English language.
I bought my niece a Kindle that just arrived and I'm about to load it up with books to give it to her tomorrow for her birthday. I've decided to be a sneaky uncle and include good books that can teach better abilities to think or at least to consider science cool and interesting. She is currently in the 4th Grade with 5th coming after the Summer.
She reads basically at her own grade level so while I'm open to stuffing the Kindle with books to be read when she's ready, I'd like to focus on giving her books she can read now. Ender's Game will be on there most likely. Game of Thrones will not.
What books would you give a youngling? Her interests currently trend toward the young mystery section, Hardy Boys and the like, but in my experience she is very open to trying new books with particular interest in YA fantasy but not much interest in Sci Fi (if I'm doing any other optimizing this year, I'll try to change her opinion on Sci Fi).