"If you want to build a ship, don't drum up people to collect wood and don't assign them tasks and work, but rather teach them to long for the endless immensity of the sea." Antoine de Saint-Exupery
They are all classic AI papers, that try and encourage the reader to think about unsolved problems.
Code Complete is a problematic book. It has some good ideas but also has some very bad ones (cone of uncertainty, 10 times productivity in good programmers, etc).
Design Patterns is mostly obsolete. Functional programming techniques made a lot of Object Oriented techniques irrelevant (e.g.: observer pattern vs callbacks with lambdas).
Art of Computer Programming is the book everyone mentions but no one reads. A classic that people actually read is Structure and Interpretation of Computer Programs.
My recommendations: "Code" by Charles Petzold,"Don't make me think" by Steve Krug, Working Effectivelly with Legacy Code, by Robert Feathers, Clean Code by uncle Bob,..
Also any book that covers soft skills aspects while emphasising the importance of having good career plans and good mentors is critical.
It's a great book simply as a book. It's something people tend to rationalize not buying. That makes it a good gift. It will provide a lifetime of reading and learning (just as it has provided Knuth a lifetime of writing).
And it meets the spec: there's no more solid foundation and it is language independent. It's plausibly one of the most important books of the 20th/21st centuries.
For more background; "Software Fundamentals: Collected papers by David L. Parnas" is a great resource.
For a tour of the CS aspects; see "Specifying Software: A Hands-On Introduction by R.D.Tennent"
If you're after something more technical / textbooky, SICP, for its combination of rigor and playful enthusiasm.
Other than that, The Art of Computer Programming set. ;)
Working Effectively with Legacy Code by Michael Feathers
Our standard text for SE was Software Engineering by Ian Sommerville.
I'm still trying to get this off the ground, so they get free support from me (ex Google / Fb / startup -> acquisition engineer with 12 YOE)