Michael Sipser's Introduction to the Theory of Computation is an extremely friendly introduction to theory of computation, including complexity theory and computability theory. As opposed to Garey and Johnson, it seems broader and shallower, covering computability theory (incl. space complexity and other non-NP-Complete topics) as well as complexity theory, and probably in a much friendlier fashion. It's one of the few compsci books I've ever read that I would describe as a "page turner": it was so interesting and readable that I couldn't put it down when reading it, and I still like to pick it up from time to time just to reread sections for pleasure.

[The 1st edition is much cheaper than the 2nd edition for anybody interesting in buying ($10-$20 used, versus >$55 used on 2nd edition or $115 new).]