Another classic is Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. As you may know, NP (which stands for "nondeterministic polynomial time") refers to a set of problems that are computationally very difficult but whose answers can be checked in polynomial time relative to the size of their input. Whether all such problems can be solved in polynomial time (P=NP?) is one of the greatest unsolved questions in computer science.
Garey and Johnson (as the book is referred to) is about NP-Complete problems, members of NP to which all other members of NP could be reduced. The book catalogs problems known to be NP-complete, including proofs that they are members, usually reductions from other NP-complete problems.
Published in 1979, the book is somewhat outdated but is still regarded as a classic . (Google Scholar lists about 60,000 citations.) The introduction (available online), in which an employee explains to their boss why they can't provide a simple solution to a problem, is also classic.
Disclaimer: I am not a theoretical computer scientist. I welcome comments from any.