What Books Should Everyone Read?
Computational Complexity:

If you are looking for recent complexity textbooks. The following two are must have.


Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak (Textbook homepage)
Computational Complexity: A Conceptual Perspective by Oded Goldreich (Textbook homepage)


The majority of the content between these two books is comparable. However, some key differences exist: Goldreich devotes more space to exploring the conceptual and philosophical basis of complexity theory, whereas Arora/Barak covers a wider selection of topics, including concrete models of complexity, quantum computation, and circuit lower bounds that are mostly absent from the former.

Another option, an older but timeless textbook in complexity is:


Computational Complexity by Christos Papadimitriou


Papadimitriou's book is notable for chapters covering first-order logic as well as the classes SNP, MaxSNP$_0$, and APX (the theoretical foundations of hardness of approximation), which are missing from the more modern texts.

Another (comparatively) old, but quite notable classic is:


Introduction to the Theory of Computation by Michael Sipser


This is one of the few/first textbooks that explicitly includes "Proof Idea:" between "Theorem:" and "Proof:", and is one of the best-written mathematical textbooks on any topic. On the other hand, it is only an intro to complexity, devoting only one 50-page chapter to "advanced topics" (including approximation, probabilistic algorithms, IP=PSPACE, and crypto). As a first book on complexity, or as an example of truly excellent writing, this book is great.


The Nature of Computation by Cristopher Moore and Stephan Mertens


Scott Aaronson writes that this book has "the fun of a popular book with the intellectual heft of a textbook." It tells stories and gives lots of entertaining examples and references (Game of Life, and lots of other examples for Turing-complete machines).
It doesn't go too deep into complexity theory but has great breadth. Especially of note are its connections to statistical physics.