- The Pragmatic Programmer, by Andrew Hunt & David Thomas: How to not suck at programming.
- Algorithms, by Robert Sedgewick: Stick to the early C or Pascal editions, later ones are full of language-specific Java, etc. distractions.
- Programming Pearls, by Jon Bentley: Short snippets of how to design & optimize.
- SICP: Just do every exercise, take it seriously, you'll learn super powers. Watching the lecture videos alongside is helpful, but the book and problem sets are mandatory.
- BASIC Computer Games, by David H. Ahl: The type-in listings are fairly hard to read & understand to newbies now, I suspect, but it's still the master class in how to decompose gameplay problems into low-level programming.
Videos and podcasts won't help you, they're pleasant noise but you learn to program by programming, by taking a problem and solving it.