The SICP MITOpenCourseware and associated Brian Harvey CS61 Berkeley lectures are both on YouTube - and the 2nd Edition PDF is currently free from mit.edu:
Big +1 for Code by Petzold. Just started the 2nd edition that came out last month and I'm blown away by Petzold's ability to pack in meaningful, interesting information without sacrificing readability.
Structure and Interpretation of Computer Programs aka. SICP.
Designing Data-Intensive Applications by Martin Klepmaan.
The C Programming Language by K&R.
Distributed Systems by Tannebaum.