Hum... respondendo ao teu desafio, confesso-te que na minha opinião não há linguagem certa para a tarefa, isto é, qualquer que seja a linguagem que escolhas irás deparar-te com problemas ao nível da aprendizagem, e digo-te isto por experiência. Concordo com a introdução da programação mais cedo nos cursos de vertente tecnológica, mas penso que ao nível superior é necessário ou será sempre necessário efectivar essa aprendizagem e dessa forma terias que dar de novo conceitos de programação.

Um dos aspectos que me preocupa enquanto docente é que a linguagem ao invés de servir como auxilio de aprendizagem consuma ela própria ou se torne de alguma forma como o objecto de estudo, ou seja, a linguagem que se escolhe para introduzir os alunos à programação deve ser o mais transparente possível e nunca ela própria ser alvo de grande estudo! É que no final destas cadeiras o que se pretende é que os alunos levem consigo fundamentos de programação, como variáveis, ciclos, vectores, ponteiros, estruturas e afins e não esta ou aquela linguagem. 

Pessoalmente acho que as linguagens funcionais, por se aproximarem mais da matemática são mais transparentes, mas não tenho certeza que sejam melhores ou piores para ensinar Introdução à Programação ;)

Eu votaria qualquer coisa derivada do Lisp se pudesse, tipo Haskell or Arc, ou então Perl por ser mais flexível, no sentido em que daria alguma liberdade aos alunos sobre como iriam implementar ao invés de algumas linguagens mais restritivas como o C por exemplo... onde a linguagem é tão restrita que se torna ela própria no elemento de estudo! ;)