One to be updated in the future. Will create a category for Theory and Fundamentals at some point. Having written a fair amount of high-level language code, VB6 and C#, I figured getting to grips with the fundamentals might not be a bad idea.
Here are a few titles that have 'moved me' in this direction.
1) Write Great Code, Volume 1 - Understanding the Machine. Randall Hyde
Randal Hyde has produced an excellent text that covers the basics of numbering systems, machine organization, instruction set architecture, I/O and more. A really enjoyable read (from the computer bookshelf of course).
2) The Art of Assembly Language. Randall Hyde
While I guess some people might suggest that a good place to start learning to write assembly language applications for Intel x86 CPUs is with MASM, Randal Hyde has created his own assembly language called HLA. HLA compiles to MASM and the principles of assembly language development are demonstrated well in HLA.
3) The Art of Computer Programming Volumes 1-3. Donald Knuth
Randall Hyde refers to the Knuth regularly in his books. Knuth’s work is relatively new to me (having graduated in a non-CS subject) but the impact of his work is easy to see in what can only be described the definitive description of computer programming. Will be chipping away at this one over the next year or two no doubt.
4) The C Programming Language. Brian W. Kernighan, Dennis M.Ritchie
Referred to as K&R. Another classic (from the inventor). Especially good when combined with a set of accompanying notes by Steve Summit at http://www.eskimo.com/~scs/cclass/krnotes/top.html
5) Absolute C++. Walter Savitch. I've learned more, indirectly, about the .Net framework from this book than I ever thought possible. An excellent text and another classic.
There are hundreds of other classics out there and of course many more that cover other subjects like object oriented programming, analysis, design, project management as well as all the high-level languages. I chose the books above specifically to help fill the gaps in my non-CS programming background. My current ‘working’ interests are in .Net, ASP.Net and C# with several large projects completed to date.
Two last must reads that are not pure programming books per se are:
PeopleWare, Productive Projects and Teams. Tom Demarco and Timothy R. Lister.
(I've heard is a standard text in the stationary cupboards of Microsoft)
And...
The Mythical Man-Month: Essays on Software Engineering, 20th Anniversary Edition by Frederick P. Brooks
Whether you're selling software, writing software, or managing teams of people that write software for a living - please read these two books. They're an oasis of insight and common sense in a desert of idiots.