Thanks for the pointers to the existing questions. The answers to those are rather different to what I understand you want though. I'll give you some suggestions from my own experience. My own degree is in physics, do I came to the field with gaps around formality, correctness/verification, algorithm analysis, dynamic programming, database systems, and to a large extent in the beginning, selection of data structures and algorithms. The most obvious gaps (e.g. data structures and algorithms) I closed early but I still read books in that area, to deepen my understanding, see alternative presentations, and refresh my memory. (I'm around 40, so books work for me :)
Here's a reading list (in no particular order other than it's the order they came to mind).
- Programming Pearls (Jon Bentley)
- More Programming Pearls (Jon Bentley)
- The Art of Computer Programming (Donald Knuth)
- Algorithms In C++ (Robert Sedgewick)
- The Algorithm Design Manual (Steven Skiena)
- The Practice of Programming (Kernighan and Pike)
- Elements of Programming (Stepanov)
- How to Solve It (Polya)
- Structure and Interpretation of Computer Programs (Abelson and Sussman)
I also got a lot out of Writing Solid Code when I read it in the mid-90s. But it's not in the list since it doesn't really relate strongly to thinking skills as such (it deals more with designing APIs to minimise the chance of accidental incorrect use - or at least that was my main take-away from it).
I also got a lot out of Gödel, Escher, Bach (Hofstadter) as a teenager, but it's already mentioned in the answers to the questions you already pointed to. It's a book to read for pleasure, rather than directly to develop one's computer science skills.
I work with a pretty large number of talented programmers, and almost universally they are fans of Programming Pearls. Certainly I wish more of the candidates I interview had read chapter 4 of that book.