Hey Ned -
Welcome to the site...
Have you seen the Green Science kits by 4M...they are probably good for the age you are talking about - a good introduction before moving onto the LEGO offerings - http://www.4m-ind.com/products.php?type=1
I've done both the solar and the tin can robot with students around 6-7 years: so with you at hand they should be right.
Of course...then it is on to LEGO WeDo... http://www.legoeducation.us/eng/product/lego_education_wedo_robotic...
And then windstorms and arduinos and raspberry pi and beyond...
Daniel! This is awesome! Thank you so much for the suggestions! It doesn't look like I can order off of 4M. Am I missing something? The Lego stuff looks really awesome, but more advanced for my little guy.
Thanks again for your suggestions!
Have you tried WeDo? We started to use WeGo lego with Sctarch programming language with kid about half a year older then yours', so you can try. You can look for links and technical details here.