If I had to pick one area that would give you the most coverage of the topics that you mentioned, it would be compiler theory. Writing a compiler will require you to understand how programming languages interact with the machine - what they are doing with the registers, how they use the stack and heap, how they translate to assembly language. A good compilers book will also provide a bit of coverage on functional languages as well, and of course you will need to also understand some type theory.

I would recommend buying one of Andrew Appel's Modern Compiler Implementation ^[1] books and working through it (I am doing this right now). It walks you through building a fully-functional compiler step by step without quite spoon-feeding it to you. You will also need a supplementary resource on assembly language; there are many available.

IMO, the most important area that you mentioned not covered in writing a compiler is a good understanding of algorithms. For this, Steven Skiena's Algorithm Design Manual ^[2] is very good for a beginner. My recommendation here would be to go through the book and implement the algorithms it discusses in whatever programming language you like. For more advanced reading, there is also the quintessential algorithms text Introduction to Algorithms ^[3] (CLRS).

Edit: looking at the larger number of answers that have been posted (with surely more to come), I'd like to emphasize that "CS fundamentals" can encompass a very broad range of topics, depending on your definition of fundamentals. I would advise you not to get overwhelmed, and instead focus on one specific area at a time. Give yourself a project (one of the two I mentioned, for instance), work through it fully, and then figure out where you'd like to go next.

Work through Structure and Interpretation of Computer Programs ^[1]. It will teach you everything that you're missing at the moment, and it's fun!

It doesn't assume that you know how to program, but it also won't treat you like an idiot. From your background, I think that virtually everything in there will be new and interesting to you.

Donald Knuth's The Art of Computer Programming ^[1] will give you all the theory you can handle. I've just started reading it with hopes to learn theory as well and have found it surprisingly approachable.

In the introduction he recommends the book to anyone who has written "at least three programs". It is structured in such a way that all the hardcore math / proofs are at the end of the chapter so that they can be skipped if that isn't what you want to focus on. There are also huge amounts of exercises all rated based on difficulty and amount of time they should take to complete - so you can learn by doing if so inclined.

I found the clause about the recommended prerequisites on the first page of the preface: "These four prerequisites can perhaps be summed up into the single requirement that the reader should have already written and tested at least, say, four programs for at least one computer."

The ideal book for me would use the high level knowledge I already have to help explain the low level stuff.

Not sure many, if any text's exist that teach from this perspective, but I'm curious if someone has links or resources to one.

If you could find the patience and time to work through something like Assembly Language for Intel-Based Computers ^[1]. I think it would open your mind to a lot of CS fundamentals. By Chapter 9 it starts to get Windows specific, but the prior 8 chapters are full of excellent information. Granted this is very low level.

I'm starting to stray here, but I just keep thinking back to really great books I've read in my travels:

The Art of UNIX Programming ^[2]

Programming Pearls ^[3]

If you live near a major university, you might inquire about being allowed to audit certain CS courses intended for junior undergrads. You'll learn a lot more hands-on this way.

Another alternative would be to acquire a syllabus for such a course at a school nearby where you could purchase the book and potential lab materials if necessary. You're going to find that your knowledge of high level programming is going to be moot when it comes to learning about the underpinnings of the architecture. However, once you learn the architecture, a lot of the "why this makes sense" junk is going to fall into place.

This book is cheap, recent, compact, good, and has course material/code/emulators online:
http://www1.idc.ac.il/tecs/

You build circuits from logic gates, a simple computer, assembler, os, compiler for a high level language, etc.

To be clear, you build virtual hardware using the software simulators they supply on the book's home page.

Introduction to Algorithms by Cormen et al, is a decent and widely available text on algorithms.

The ideal book for me would use the high level knowledge I already have to help explain the low level stuff.

I think you should stick with the 'beginner mind' and approach things as an (almost) absolute beginner. I found this to speed up learning. I'm also self taught (got a CS degree, but just because it seemed that piece of paper is useful, I didn't learn that much in 'official' studies).

As for a book recommendation, there's a book I tend to recommend a lot: SICP, http://mitpress.mit.edu/sicp/ (full text available online).

It is both high and low level - and I also believe it is hard enough to keep you entertained. As a bonus, your practical experience has probably taught you little of what they are describing. Just don't expect to be using what you learn from it directly - it teaches a lot of stuff that's indirectly extremely useful by changing the way you look at what you know or have to approach.

There are also some nice videos at http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/, but the essential experience here is reading the book and working on the exercises.

IMO you're interested in too low level, that information isn't so much relevant to software development at all any longer unless you're going to work with embedded systems or write drivers perhaps. I would recommend learning original C instead so you can learn pointer arithmetic and memory management. That is far more important to understand especially since you've worked with managed programming languages that have handled all of the memory management.

Aside from that, object orientated design and understanding how to apply patterns and learn new tools and frameworks is substantially more relevant to modern software development than being able to code in assembler.

I think learning at least some assembly language is very useful in understanding how many languages work. I remember people having a lot of problem with things like pointers in C, but if you've done assembly language it all makes sense.

There are a lot of good suggestions (e.g. SICP), but most of them are pretty heavy (e.g. Knuth, Dragon Book). If you want to start with the heavy, definitely grab a book on Discrete Math and possibly algorithms first.

If you're looking to start a bit lighter, I found Write Great Code ^[1] I and II to offer a great introduction to the concepts you're interested in, and it's designed for precisely for someone in your position.

I think the whys are very important to a self-taught programmer learning new tricks. You can't just read a book that says "do it this way" because the unconscious question is always there; why should I do it this way, instead of the current way I do it, when a new method will take longer? How do I integrate my strengths with a new methodology? What will I get out of doing so?

I can't suggest specific books at the moment, but if you vet your books by checking that they get into the reasons behind the theory and comparison between methods, you may have some luck.

You might want to check out Write Great Code: Understanding the Machine ^[1]. I own this book but have not yet read it, so I can't say for sure it meets your needs. The Amazon.com reviews speak highly of it however.

For a completely different angle of attack, I'd suggest The Pragmatic Programmer. It's less about the hardware details, and more about being a software developer. Good stuff.

MIT and Berkeley (and others) publish podcasts of undergraduate CS courses.

For example http://webcast.berkeley.edu/course_feeds.php

You can find them on itunes.

There is a great book Called write great code ^[1] that will help to explain how the machine works. For CS topics the gold standard is The art of computer programming ^[2], but if you don't have some higher level math in your background you might find it a bit challenging. Reading the algorithms and pattern question here will give you a set of topics to research.

I don't know of any specific resources to answer your question, but I can give you some pointers on where to look.

If you are interested in low-level concepts (registers, gates, stack, assembly language, embedded systems), you'd find most of the knowledge in a computer engineering curriculum that's heavy on electrical engineering concepts. You might try trawling the websites of great universities to see what lecture notes are available. Any of the books that I used in college would be overkill for what you probably want, so I won't recommend them.

For the algorithms, UNIX, and functional language topics, you can try the above strategy for the computer science curriculum. MIT has some particularly good podcasts ^[1].

LectureFox ^[2] also has a lot of good resources, mostly videos and notes.

If you have specific questions about these topics, post them here and see what kind of an education StackOverflow can provide!

I agree with Mr-sk that Irvine's book on assembly is a good book. If you're interested in learning more about some additional topics such as computer architecture, and how linking, memory management, and some other more non-language specific parts of how computer science works, take a look at Computer Systems: A Programmer's Perspective ^[1]. I think it's one of the best books I had as part of my undergraduate (and graduate) CS education.

I will agree with Mr-sk about SICP ^[1]. Be sure the read Peter Norvig's review on amazon to understand what you are getting into before you buy the book. Working through it is an challenging mind expanding experience.

Echoing on a comment attached to this answer ^[1], I highly recommend David Malan's CS50 Video Podcast ^[2]. [The production quality and editing are superb!]

I think it's superior to other competitive offerings in this space, and I think he (quite possibly better than anyone else on Earth) fulfills the promise of online education.

Try writing a language interpreter, or other complex program. This requires different types of components, and so much code, that you begin to see parts of your own code, as other programmers do, when you go revisit parts. You will see how having a clear design pattern for a component makes it extensible and flexible. You will need some form of source code version control as you put aside and resume parts of the program.

Write the interpreter in C. You can get the C Programming Language, by Kernighan and Ritchie. This book is a minimalist masterpiece. Get the oldest version you can get of this book, before ANSI C is included, and bloat begins to invade.