Just found my old Usborne Electronic Workshop book "How To Make Computer Model Controllers for C64, VIC 20, Spectrum & BBC". There was also a robot one in the series but I do not have that.
Re-reading the book now I still remember doing some of the projects over 25 years ago.
The book is a good mix of practical hardware, coding and "fun" things to do.
For instance sensors are made using nails and drawing pins as contacts (the child can therefore see the switch working instead of just buying a microswitch).
There are good chapters on the theory of relays, resistors etc.
Everything is soldered to Veroboard so, again, the circuits are easily traceable. Instructions are included for making the cables to connect to the user ports of the computers - along with dire warnings about wrong connections ;o)
The programs include allowing trains to be found on a track, races to be run, "fuel" to be added to scalextric cars (the power is cut if you run out of fuel) etc.
I think these type of exciting "real" projects are ideal for the Pi (& Gertboard) as they allow children to experiment and play with real hardware and immediately see the results.
Perhaps a community-contributed library of starter projects will inspire the current generation of children. My 6 year old loves machines and robots - we will both be playing with my Pi when it arrives & doing very similar things to those in the book.
As for the programming language - I don't think it matters. Use the one most suitable for the project - the logical thinking is the important and difficult part, the nuances and syntax of a particular language are easy to learn. Personally (although I am an Engineer not a programmer) I started with the ZX81, then BBC Basic, FORTRAN and various object oriented languages. I use the tool for the job, sometimes it is a properly coded application, sometimes just a quick and dirty bash or powershell script. Last week I dusted off my FORTRAN skills and wrote a couple of applications for a client that saved them hundreds of hours of manual data manipulation. Why did I use FORTRAN? They use specialist software written in FORTRAN which uses formatted input without robust error checking. As I don't have the source code for the specialist software I analysed the required formats and used this to write FORTRAN format statements to generate text files in the required format. This was easiest in the same language as the original application.