Pues yo, por poner la nota discordante un poco, te voy a hacer otra recomendación:
Yo, en la carrera, comencé a programar en MODULA-2. Es un lenguaje que no lo conoce ni su madre (bueno, tampoco tanto, pero casi), pero que creo que es de lo mejorcito para aprender estructuras y demás de programación. No vas a conseguir hacer nada muy bonito con él, no hay casi bibliotecas (o no había), etc. Pero es MUY BUENO para aprender a programar, porque es tremendamente didáctico (de hecho, para eso es). Si sientas bien las bases con este, el resto te será muy sencillo (el tema de POO, quizás, sea lo más flojo pues no es POO propiamente dicha). Y que conste que yo al principio echaba pestes de aprender un lenguaje que no tiene "aplicación en la vida real".