You should check out Alan Kay's Squeak - http://www.squeakland.org - which was the highlight of his (second) talk at the Interaction Design and Children conference.

The piece he showed us involved dragging and dropping items to create rules for an object you create by simply drawing it. For example, he drew a car and made it drive in circles, then a steering wheel to the side, which he then associated with the car so he could steer it, etc. etc. Basic principles of programming, all through a fun interface.

Thanks Jason, exactly what I'm after. When I get a few more I'll update the main post.

Matt,
You may remember the work of Seymour Papert and associates from the investigations and reports of Sherry Turkle in _The Second Self_.

A clip from a richly linked site:
The Logo programming language is an adaptation by Wally Feurzeig and Seymour Papert
Dr. Seymour Papert [...]
One could say that Logo is Lisp without the parentheses. Today, it is known principally for its "turtle graphics" but it has significant list handling facilities, file handling and I/O facilities and can be used to teach most computer science concepts, as Brian Harvey does in his "Computer Science Logo Style" trilogy.
http://encyclopedia.thefreedictionary.com/Logo%20programming%20language

Colleagues here at RIT, led by my friend Andy Phelps, are working on a project called Muppets

http://muppets.rit.edu/

From the first page:

What is MUPPETS ?

Through capitalizing on research in the areas of gaming and virtual community social psychology, RIT is engaged in a project to develop a Collaborative Virtual Environment (CVE) entitled “The Multi-User Programming Pedagogy for Enhancing Traditional Study” (MUPPETS). The MUPPETS system will be aimed specifically at engaging upper-division students in the education of lower-division students through their first-year programming core. The MUPPETS team is building upon existing research and technical developments in the field to design and construct a CVE and supporting infrastructure that allows students to write very simple Java® code similar to, and constructed around the same pedagogical issues as, code written in a more traditional course of first year study.

As part of the MUPPETS system, however, this code can now control objects in a shared virtual world very much like an online massively-multiplayer game that many prospective students are already familiar with. Upper level students also populate the system in a structure of their own, and this population will be aimed at encouraging and rewarding student engagement and peer knowledge-transmission.

Best advice I can give from experience is: Get your hands on a circuitry pencilbox. Basically everything I know about the inner workings of computers -- which could about fit in a pencil box, admittedly -- comes from my freshman year of high school, learning Boolean logic and then manipulating wires and chips to simulate "and" and "not" and "exclusive or" gates and... um... J/K flip-flops (I think) and so forth. We did that before we ever learned any programming (in high school... I'd done some earlier), and it was absolutely invaluable. Completely strips away any mistakenly holistic notions about how computers work. Even LOGO, which we did in sixth grade, was a mystery to me until I had to translate complex operations into electrical impulses myself.

Following up on Francois' post: I believe that Squeak is at least in part built upon/with Logo and stems from Kay's work with Papert and Marvin Minsky.

Jeliot 3 is a program animation tool oriented to teach programming to novices. The animation consists on showing how the expressions are evaluated and how that changes the program behavior and the data structures.

You can have a look at http://cs.joensuu.fi/jeliot

Mind the typo (first line under "Updates"):
"Via Jason: Suqeak, by Alan Kay..."

As I understand it Alan Kay's development of Smalltalk involved bringing children in and trying to reimagine what a programming language would look like. This is from Rheingold's _Tools for Thought_, "Part of the Smalltalk project's effect on the early days at PARC was inspirational. It wasn't long before the rest of the team understood Alan's desire to bring children into the process of designing the same instrument that he and all the other computer scientists wanted to use themselves." (http://www.rheingold.com/texts/tft/11.html).

Another language that preceeded Proce55ing and is simpler is Design By Numbers by Maeda. See http://dbn.media.mit.edu/whatisdbn.html where there is an online interpreter you can play with.

An online book that Steve Ramsay turned me onto is "How to Think Like a Computer Scientist" (http://www.ibiblio.org/obp/thinkCSpy/).

Finally you should look at the Lego robotics Mindstorms kit and the various programming environments for it.