Know and Love:
Logo - where oldest started
Alice - 3D programming/animation - oldest tried this for awhile but liked Game maker better.
Game maker - fun place to start, using basic block building, and as you get more experienced you can look into text based programming.
Python - Hello World is a good book to start with. Try the Python Challenge for programming and math fun.
Roblox - OK, I don't know and love this, my oldest does, and he swears if you make games (as opposed to play them) it's educational. Forewarned - kids are making the games available for play and there are plenty of shoot 'em up type stuff. To learn more about programming, check out the roblox wiki, and to learn more about scripting with Lua check out the Lua Help.
Minecraft - technically, this is not programming, it's a computer sand box game, but people mod it, and you can often tweak the mods. As you get more experience you can script using Java. DS13 says "If you're interested in modding, poke around the mindcraft.jar"
Scratch - block based programming. My youngest has played with this, but my oldest hasn't so I don't have a good review of it. It looks like a drawing/animation game to me, but I'm informed I'm wrong.
Unity - this recommendation came from a cousin (who makes app games for a living) as a way for someone already familiar with basic programming to make more powerful games. He recommends " it's a great tool for making games with a strong community, and very easy to get started." I haven't convinced ds 13 to give it a go yet.