I also like Papadimitriou's textbooks: Elements of the Theory of Computation and Computational Complexity.