I'm going to go on a slightly different route here: Lego Mindstorms. No, I'm serious. Kids need to play with Lego anyway. I think it's one of the best toys to express creativity, explore physics, mechanics, and all that good stuff. It's fun to look at, to touch (and unfortunately also to swallow, so you have to be a bit careful with that part).
So Lego Mindstorms is natural extension. They'll learn programming, electronics, robotics, etc. They'll have fun doing it, and they can show off their creation to everyone (it's universal that everybody thinks robots are cool!).
Blah-blah-blah I can go on and on but I truly think this is the best way to do it.
I'll write a bit more: the other reason why this is the best way to do it is the ease of transition. You give them regular Lego, they'll quickly pick it up and play with it. They'll explore their own creative minds, etc, but then realize the limitation of inanimate dumb objects. So, driven by their own desires, they'll gravitate to Mindstorms naturally, and discover more and more cool things as time goes on.
I don't think you get this kind of fun self-motivating learning curve by sitting a kid in front of a computer right away.