Hay tantas opiniones como culos. La mía es que a programar se aprende programando.
Comenzar con libros como "How To Design Programs" o "Structure and Interpretation of Computer Programs" o la "Metodología de la programación" y leerlos de principio a fin es un camino por supuesto pero para gente muy centrada que no se desanime con facilidad. Depende como sea el autodidacta...
Así que descartando este enfoque creo que lo mejor es ponerse a hacer código desde prácticamente el primer día. El mejor lenguaje para aprender probablemente sea Python -
Python Programming Language – Official Website - Puedes empezar simplemente descargándote Python y utilizando el notepad/notepad++/ultraedit para escribir el código. Más adelante podrías descargarte el IDE de Python.
Hay un millón de libros pero creo que uno bueno para empezar es:
"Python Programming: An Introduction to Computer Science" de John Zelle.
web con recursos de descargas del libro:
http://mcsp.wartburg.edu/zelle/python/
y en paralelo puedes mirar esto que creo que va como anillo al dedo para ir haciendo mini-aplicaciones cada poco tiempo a la vez que se va aprendiendo:
Invent Your Own Computer Games with Python
Además en la web hay millones de enlaces que te pueden servir. Google es tu amigo.
Ejemplos:
A Gentle Introduction to Programming Using Python | Electrical Engineering and Computer Science | MIT OpenCourseWare
que enlaza al libro
http://www.greenteapress.com/thinkpython/thinkCSpy/thinkCSpy.pdf
Otra web
Learning to Program
o esto:
Python
y por supuesto todo la documentación oficial de Python + cualquier otro libro que encuentres y te guste.
=======================
Una vez hayas finiquitado el material de arriba te aconsejaría que te interesaras por los patrones de diseño (design patterns). Me parece excelente (aunque los ejemplos estén en java) para un principiante este: "Head-First Design Patterns". La razón: los libros de Head-First son libros entretenidos de leer, nada "académicos".
En esta segunda fase quizá sea un buen momento para comenzar a trastear con java. En la línea del anterior: "Head First Java"
o uno de estos más "serios":
"Thinking in Java"
"Effective Java 2ed"
--------------------
Lo de los patrones de diseño te lo decía porque te debería valer para cualquier lenguaje y saber algo de java nunca es una mala idea.
=======================
Aparte, en cualquier momento como recursos genéricos tienes
Tutoriales + código fuente
SourceForge - Download, Develop and Publish Free Open Source Software
Web de preguntas/respuestas
Stack Overflow
========================
Por último libros que creo que cualquier programador debe leer sí o sí (para más adelante):
"Code Complete"
"The pragmatic programmer"
y hay muchos más, me vienen a la cabeza los de Martin Fowler, pero ya dependerá de lo cómodo que te sientas cuando llegues a este punto y de cuales sean tus objetivos. A lo mejor te interesa la programación web, a lo mejor quieres ir duro a aprender C, quizá te interese alguna plataforma móvil (Android/IOS de apple). ¿Cual es el objetivo?
=========================
Lo dicho,
1. Bájate Python.
2. Escribe tu primer programa "Hello World".
3. Ejecútalo.
Con internet todo lo demás depende del tiempo que le eches.
) 
:
