The Sipser book is excellent. It's one of only a handful of textbooks I decided to keep after I graduated from university. And perhaps the only one I kept because of how good it was rather than because the campus bookstore wanted to give me a pittance for it... and I didn't even buy the book until after the semester when I had to return the copy I'd checked out from the library...
I later on picked up the first two editions of Hopcroft & Ullman for $1 each at a used book store. I don't think either edition can really hold a candle to the Sipser book, which is shorter, more thorough, and (imo) easier to understand.
One caveat: it's super-expensive. I'd recommend finding a used copy or even an "international edition" (which will be soft-cover rather than hard-cover, but the content is the same).
I bought Sipser for this very purpose. I found it very difficult without being able to discuss it with anyone to clarify my understanding of the ideas. I would love to work through it, but would need a CS tutor to help me... any takers? ;)
Edit: to be honest it's the maths notation that is a big barrier for me. Until one can read it relatively fluently it's very hard to translate the ideas into a meaningful mental model .
"Meta Math!: The Quest for Omega" by Gregory Chaitin [0] was my introduction to the theory of computability [1]. I found it enjoyable and approachable.
This 10 minute video is a great introduction to the P = NP problem and computational complexity theory if you have no context. I've shown this to plenty of friends (including those outside of computer science).
Essentially, "does being able to quickly recognize correct answers mean there's also a quick way to find them?"
Here's a short-ish overview: http://www.math.uchicago.edu/~may/VIGRE/VIGRE2011/REUPapers/...
For a more extensive overview, try this textbook by Michael Sipser (Amazon Affiliate Link if feeling generous: http://amzn.to/2fy9tKZ, Google Books link otherwise: https://books.google.com/books?id=1aMKAAAAQBAJ&dq=introducti...).