Quantum Computing Since Democritus, by Scott Aaronson. It covers an astounding amount of stuff -- including complexity theory, the nature of randomness and information, and quantum information theory -- into less than 400 pages.
Within computer science, I found "Introduction to the Theory of Computation" by Sipser to cover a lot of ground in a concise and comprehensible manner.
It's a great book (I'm more than halfway into it) but definitely not for laymen. I followed one quantum computing class as well as having had many QM classes and I find myself having to read a lot of background information to understand Aaronson. He writes well, but I lacked the proper computability knowledge to really enjoy the book in one go.