Iwould also definitely give Python a try, I have personally seen Python as a basic language to start learning how to code in action and it is very effective to teach the basics of program. Zed Shaw's book is a very interesting way to learn progamming with Python, though I don't have any references about it's effectiveness... http://learnpythonthehardway.org/

If you want to do something a little different you can also try subsetting Haskell as per in most of the courses found in http://www.haskell.org/haskellwiki/Haskell_in_education#Hask... That is the approach they take in the University I studied CS, and it's an interesting one to combine with learning Python as a fist language.

Also, be wary of EWD quotes about teaching computer science, since they are sometimes a bit cocky.

youtube.com has some great classes by Google on python. search for 'google python class'.