Lego Mindstorms are excellent. I haven't tried their more recent stuff, but it looks very good. Combining the ease of design and assembly of Legos with robotics... I spent hours building, rebuilding, and programming my set. Could not recommend anything more.
I agree, Mindstorms are really good. If they're not that used to programming yet they can start off using the graphical programming language (NXT-G). Then, when they're ready to really dig in, they can start using C.
