Q:

Theoretical CS and Math - self-study recommendations

I am a non-CS grad and my field of study is unrelated to CS. However, as part of a larger plan to become a computer scientist, I want to obtain a solid background in theoretical computer science and math as it relates to CS. I did a plenty of research and selected the following best/really good books on the topic of CS and math and would like to ask for your opinions on:

Completeness of topics covered (please recommend anything I've missed)
Overlap of material covered / overkill area (please recommend books that should be removed from the list)
Order to study the books (I listed in the order that I think they should be studied)

The list feels excessively long, so I would appreciate recommendations to remove some books, without the loss of the core knowledge require for CS.
So, the books are:

Mathematician's Delight by W. W. Sawyer
How to Prove It: A Structured Approach by Daniel J. Velleman
How to Solve It: A New Aspect of Mathematical Method by G. Polya
An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson
Foundations of Computer Science by Al Aho and Jeff Ullman (http://i.stanford.edu/~ullman/focs.html)
Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik
Introduction to the Theory of Computation by Michael Sipser
Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
Computational Complexity: A Conceptual Perspective by Oded Goldreich
Computational Complexity: A Modern Approach by Sanjeev Arora, Boaz Barak
A Course in Combinatorics by J. H. van Lint, R. M. Wilson
Computability: An Introduction to Recursive Function Theory by Nigel Cutland
Computers and Intractability: A Guide to the Theory of NP-Completeness by M.R. Garey, D.S. Johnson
Theory of Recursive Functions and Effective Computability by Hartley Rogers
Inequalities by G.H. Hardy, J. E. Littlewood, G. Polya
Mathematical Logic: A Course With Exercises (Part I): Propositional Calculus, Bookean Algebras, Predicate Calculus by René Cori, Daniel Lascar
Mathematical Logic: A Course With Exercises (Part II): Recursion Theory, Godel's Theorems, Set Theory, Model Theory by René Cori, Daniel Lascar

A:

Your list is extremely problematic.
To start with, I would flatly skip books 6,11,12,14,15,16,17: Books 6, 11 and 15 are general mathematics which is not really needed unless you become a theoretical researcher. Books 12 and 14 cover recursion theory which is not computer science (even though it deals with computability!). Books 16 and 17 cover advanced topics in logic, whereas you only need to know very basic logic.
Out of books 1,2,3, I would choose just one to serve as a general introduction to mathematics and proofs.
Books 5,7,8,9,10,13 cover several subjects: automata theory, algorithms, and complexity theory. Let me suggest that you follow Sipser (Book 7) for automata theory and complexity theory, and Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein ("CLRS") for algorithms.
Book 4 deals with functional programming. While my computer science education has never included any courses on this subject, it is fair to say that many researchers in theoretical computer science count functional programming as part of the essential foundations.
Summarizing: what you remain with is

One of books 1-3 (or any comparable "introduction to proof" text)
CLRS
Book 4 (functional programming)
Book 7 (automata theory and complexity theory)

A:

You might also consider taking advantage of some of the many online courses available. 
For example, both Stanford and MIT offer (free) online courses in computer science, and I think there are many others available as well.
As far as books go, I second most of Yuval's recommendations, except that
CLRS is a great reference, but a little overwhelming as an introductory book to just sit down and read through. For a first pass at the algorithms portion, I might recommend Algorithms by Dasgupta et al.. The previous link is to the free online pre-print, but it's also pretty cheap to buy in paperback. 

