Já tinha dado a minha opinião sobre este tema na lista dos MSPs e continuo a afirmar que as duas melhores linguagens para se começar a programar são Python e Scheme.

Scheme acompanhado do "How to Design Programs: An Introduction to Programming and Computing" é uma excelente introdução na minha opinião. O livro ensina como formular ideias e como "converter" para código a solução para o nosso problema numa linguagem clara e acessivel.

No caso do Python, usar o "Beginning Python" pelas mesmas razões :P

O porquê destas duas linguagens? Abstração. Ninguém no seu perfeito juizo deveria dar introdução à programação em C (no entanto acontece frequentemente, nomeadamente na minha escola). Qualquer destas duas linguagens vai directo ao assunto e facilita o desenvolvimento de software. Nada de memory management, 10 tipos diferentes de TADs, sintaxe manhosa ou bagagem excessiva (*cof* Java *cof* C *cof* C++ *cof*). 

E para quem acha que linguanges funcionais para se começar a programar é mau, a maioria das universidades lá fora (MITs e afins) usa o Scheme como linguagem nas famosas cadeiras de CS101... E pelos vistos não se dão mal...