I don't actually have any textbook recommendations for you, but with respect to Comp. Sci., keep in mind that there is a difference between Comp. Sci. and programming. Obviously there is a large overlap, and you can use a lot of Comp. Sci. theory in every day programming, but programming is a discipline unto itself.
I think programming is a lot like writing (prose). You need to read a lot and write a lot. If you want to be a great programmer, I think you should be programming every day -- not just school, or work assignments, but you own code. You need to find your own voice. It is hard to find time to do it, I know. Also, read as much as you can. Open Source software is ideal because you can read code from a lot of different authors. Sometimes people only read their own code or code from their colleagues at work. This can really stunt their growth. Sometimes I think there should be a "Programming" degree in the arts faculties at universities...
I'm not a scientist, I'm a programmer. However, the theory that I think will help you most is:
- Automata and grammars. Specifically you should know the theory, be able to make regular expressions and be able to write/read BNF. You should definitely know the Chomsky hierarchy and be able to recognize the type of grammar by looking at the BNF or code (this is especially important if you ever write a file format or design a communications protocol).
- Group theory
- Linear algebra
- Basic calculus (may or may not find differential equations useful depending on what you are programming)
- Basic statistics (definitely need to know what probability distributions are... lately I've been thinking that Bayes theorem is getting to be more and more important).
- Algorithmic complexity (i.e. O() notation).
For studying programming:
- You should be aware of design patterns and be able to recognize them in code (you don't have to go crazy on it, though). There are lots of good books on the subject. Or just browse c2 wiki.
- You should know how to do test first programming. Kent Beck's book "Test Driven Development: By Example", is arguably not the best book on the topic, but it is the book I always recommend to beginners because it is the most straight forward. Other books tend to conflate a lot of issues and to push points of view that (in my mind at least) have yet to prove themselves. Beck's book will give you the basics and allow you to move on from there.
- You should know how to make UML object diagrams. Unfortunately, I don't know of any books on the subject that deal only with object diagrams. You don't have to use UML diagrams in real life, but they contain the concepts that you can use when sketching designs.
- You should know how to refactor code that is under test. Michael Feather's "Working Effectively with Legacy Code" is the only good book I know on the topic. It is very advanced, though. There may be more gentle introductions somewhere. Martin Fowler's book is a great reference book, but it is not useful for a beginner IMHO.
These are the basics, from my point of view. I recommend also learning at least one programming language from each of:
- modular (C, Pascal, etc)
- Strongly typed OO (C++, Java, C#, etc)
- Dynamically typed OO (Ruby, Python, etc)
- Pure functional (Lisp, Scheme, Haskel, etc)
- Declarative (XSLT, Prolog, etc...)
- Assembly (microcorruption.com is a great introduction)
Obviously you won't use all of these things all the time (and some you will never use), but for me if someone has all of these things it gives them a good base to work from. I'm probably forgetting some important stuff as well, but that's enough to get you started.