I like the lego Mindworks idea - the problem with programming is getting an idea of what is going on inside the computer - what better way of showing up the differences in the electronic world and the outside world than by trying to get a computer to control a robot.
Plus I loved Lego as a kid.
I started programming on a C64 back in 81 or 82 - but back then, just getting some words to show up on a screen was exciting, let alone graphics or sound etc. I think one problem with understanding computers to day is that there are so many layers of abstraction, that it's difficult to realise exactly how clunky the workings of a computer's mind really are. Plus when you have the choice between typing something along the lines of
Code:
10 PRINT "TOM IS COOL ";
20 GOTO 10
(which at the time - for a 10 year-old me anyway - was incredibly exciting)
or slaying thousands of gun-toting freaks in a photo-perfect first-person shooter - I wonder whether I would have spent all those hours actually learning something other than how to rapidly twitch my trigger finger.
You can still get old computers on eBay, why not get the full kit (disk-drive, tapes etc) and start off retro - it might be different enough to inspire your children into learning something different. Especially since many of the programs that you used to have to shell out the readies for are now available for download etc. This is more of a project, but something I'd quite like to do properly at some point with a C64, a 1571 disk-drive, cassette deck etc - it would be like stepping back into 1984.
But now I've said too much