Any recommended books on complexity theory?
Two good sources for newer material (from the past quarter-century) are "Complexity Theory: A Modern Approach" by Arora and Barak, and "The Nature of Computation" by Mertens and Moore.
A personal, idiosyncratic favorite is "Gems of Theoretical Computer Science" by Uwe Schoning.