Following that we 'built' a computer together out of paper. This allowed me to show each part and what it did to give a base understanding. Then I let them hook up the RPi to a monitor and keyboard. The device was configured beforehand and had all the updates and software needed.
I chose not to connect it to the internet. That's how I learned computers and I thought it would be a good way for my kid to learn. Turned out really well and documentation is available on the device if you show them how to search for it.
As for educational software, I highly recommend GCompris[1]. It's just an awesome set of tools disguised as games. Accessible for a wide range of ages. I let my kid run wild in there and I'm blown away by the things it's helped teach them.
Last thing I'll mention is very specific to my interests, but I installed a few roguelikes. Easily accessible terminal games. Some well known like Nethack and others simple browser games I've made myself. All of them have gotten play time. In an age where graphics have overtaken good gameplay, I wanted to present games that weren't all lights and colors. Most of them are stripped down to learning the world and problem solving. Being turn based helps give time for them to think about each obstacle. And I feel like the constant death and resetting has helped alleviate early troubles they had with failure.
I put some buttons on a firm cardboard box and put the makeymakey inside.
I hook this up to Scratch and have it play sounds and move animations on the screen.
My son loves it. You can do a sound board and the kids will just laugh and have a blast.
I would start with a small laptop having some CLI and no GUI for the sake of getting started with basic concepts such as keyboard and text on a screen and simple utils such as Gnu Units. Then when such a computer starts being boring it's about time to introduce GUI for the sake of reading and mastering touchtyping. Then of course you will be forced to introduce multimedia. Then it will be the internet's turn. Try to resist introducing a smartphone to the child at least before acquiring the sense of good flavor because recommendation systems of nowadays are very effective in enslaving even adults.
It taught me a lot about emergent properties from simple systems (or, at least a child-like understanding of it), and the concept of having something follow I told it to do (and all the problems that arise from it).
2. Load any old text editor.
3. Put your child on your lap.
4. Point to the keyboard and mouse and encourage your child to use them.
5. Express wonder, joy and encouragement at everything they do.
6. Experience joy and wonder yourself.
Good luck.