I'm doing pretty much that right now with my 5-year-old daughter with a raspberry pi. She can currently boot it up and check her email by herself (using claws-mail). One of the big things that I think we can do today that wasn't really available when I was a kid is robotics. For a couple hundred bucks and some time invested, you can make a robot platform for them to play with and get them playing with super low-level stuff without any kind of pretense (limiting her to just the r-pi with a BASIC repl would be pretty artificial in today's world, but the state of hobby robotics now is much like the state of computing was 25 years ago). I'm working on a robot repl right now so that she can get the instant feedback like we had with BASIC, but it's slow going for lack of time.

The thing I've found interesting is how she goes back and forth between the r-pi and the iPhone pretty seamlessly. I don't think she realizes that they're fundamentally similar devices. To her the iPhone is just a black box with some fun games on it, but the r-pi is a lot more like an adventure.