Introduction to complexity and computability
For an introduction to the theory of computation I recommend you these great books (in order of increasing "complexity"):

1) Introduction to the Theory of Computation by Michael Sipser

It is very readable, theorems are very well explained and there are plenty of exercises (some with solutions and/or hints) and references.  

2) Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences) by Michael R. Garey

The "bible" of NP-completeness. Although the second part is a mere list of NP-complete problems (with hints on the reductions), the first part is a good introduction to computational complexity and is focused on the theory of NP-completeness (but there are no exercises).

3) Computational Complexity: A Modern Approach by Sanjeev Arora

... This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory, including interactive proofs, PCP, derandomization, and quantum computation....  It has plenty of examples/exercises (unfortunately some nice (advanced) topics like Kolmogorov complexity or Descriptive complexity are missing).

Finally, if you need more intermediate/advanced books on computational complexity, then take a look to Lance Fortnow's Favorite Computational Complexity books list on Amazon ...
without any doubt a bunch of "gems" :-)