Lo malo de recomendar cómo "aprender a" es que sólo se aprende una vez, por lo que cada persona sólo podrá hablarte de una única experiencia particular y aislada: si cree que le fue bien, o si cree que le fue mal.
En mi caso, yo aprendí Java y Programación Orientada a Objetos todo a un mismo tiempo, con el libro
Piensa en Java de Bruce Eckel y terminé muy contento. Creo que lo explicaba de forma muy clara y detallada.
Yo hice Ingeniería Técnica en Informática de Sistemas. En primero, en la asignatura anual de Programación, el primer cuatrimestre fue programación estructurada y el segundo POO. El primer cuatrimestre fui a clase y llevé las cosas al día, y el segundo me dediqué a la vida universitaria. Así que durante el verano me leí el Piensa en Java de cabo a regazo y saqué sobresaliente tanto en examen como en las prácticas gracias a este libro (los apuntes de la asignatura eran infumables).
Ésa fue mi experiencia, y me fue bien. Es todo lo que puedo decir y recomendar.
Tienes mil copias por internet:
Descargar Piensa en Java Gratis en PDF | Bruce Eckel
Me estoy acordando de que, por aquel entonces, había otro libro de cabecera de quien aprendía este lenguaje:
La biblia de Java. Nunca lo leí, pero conocí a gente muy contenta con él.
Ahora bien, si lo que quieres es aprender a programar por hobby, si eres de formación matemática yo me decantaría lenguajes funcionales, y si no eres de formación matemática y tienes un par de huevones también. Creo que la filosofía de los lenguajes funcionales se acerca mucho más a la algoritmia y el concepto de programación. A mí me parecen más entretenidos. No es que sean más complicados, simplemente son menos agradecidos porque suelen carecer de facilidades para interfaces gráficas y hay que cambiar mucho el chip con respecto a la programación estructurada.
En concreto te recomendaría una belleza como
Haskell. A mí se me pone dura cuando veo código bien escrito en Haskell, me parece el puñetero lenguaje por excelencia. Si la gente hablase Haskell en la vida real no habría pobreza ni malos entendidos y todo sería un oasis de tranquilidad y armonía. Alguien que no haya programado en su fruta vida pensará que estoy pirado, pero los que os dediquéis a esto conoceréis esa sensación de "Menudo código :8:". Esto es como los frikis a los que les gustan las piedras, aquí cada uno se la goza con su especialidad.
El manual por excelencia para aprender Haskell es éste, que lo tienes gratis en la propia web del autor:
Learn You a Haskell for Great Good!