It is hard to overestimate the impact of Popular Science books such as “A Brief History of Time” and “Chaos: Making a New Science” on Scientific Research. The indirect impact of popularizing Science and Scientific Education often surpass the direct contribution that most scientists can hope to achieve in their life time. For this reason, many of the greatest scientists (including in our field) choose to invest considerable time in this blessed endeavor. I personally believe that the Theory of Computing deserves more popularization than it gets (and I hope to someday contribute my share). Nevertheless, this post is meant as a tribute to our colleagues who already made wonderful such contributions. I will continuously edit this post with TOC popular books and educational resources (based on my own knowledge and suggestions in the comments).
Popular TOC books:
Scott Aaronson, Quantum Computing since Democritus
Martin Davis, Engines of Logic: Mathematicians and the Origin of the Computer
A. K. Dewdney, The New Turing Omnibus: Sixty-Six Excursions in Computer Science
David Harel, Computers Ltd.: What They Really Can’t Do
David Harel with Yishai Feldman, Algorithmics: The Spirit of Computing
Douglas Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid
Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible
Cristopher Moore and Stephan Mertens, The Nature of Computation
Dennis Shasha and Cathy Lazere, Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists
Leslie Valiant, Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World
Leslie Valiant, Circuits of the Mind
Noson S. Yanofsky, The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us
Hector Zenil, Randomness Through Computation: Some Answers, More Questions
Fiction
Apostolos Doxiadis and Christos Papadimitriou, Logicomix: An epic search for truth
Christos H. Papadimitriou, Turing (A Novel about Computation)
Other Resources:
CS Unplugged (including a book)
Windows On Theory 
Hello
I would add:
Yanovsky 2013 “Outer Limits of Reason” http://www.amazon.com/gp/product/0262019353?psc=1&redirect=true&ref_=oh_aui_search_detailpage
Davis 2001 “Engines of Logic” http://www.amazon.com/gp/product/0393322297?psc=1&redirect=true&ref_=oh_aui_search_detailpage
Zenil 2011 “Randomness Through Computation” http://www.amazon.com/gp/product/9814327743?psc=1&redirect=true&ref_=oh_aui_search_detailpage
I completely agree: popularizing TOC is an important and worthy goal. Speaking for myself, I remember reading David Harel’s “Algorithmica” as the moment when I started falling in love with TOC.
L. Valiant’s “Probably Approximately Correct” is very nice.
Hofstadter, *Gôdel, Escher, Bach,* seems like a natural inclusion.
a very worthwhile endeavor but youd be very surprised how many excellent books there are now, its somewhat exploded in recent years with the rise of CS/ internet, “algorithmic age” and “algorithmic lens” etc. note that amazon book lists might be a nice way to organize this. and it would even be cool to set up a voting system for entries.
one of my recent favorites not mentioned yet is Fortnow on P vs NP
see also what are the pop sci books that inspire CS
typo: Less Valiant -> Leslie Valiant
Christos Papadimitriou has “Turing (a Novel about Computation)” and “Logicomix”.
Moore and Mertens: The Nature of Computation http://www.nature-of-computation.org/
Vardi’s videotaped lecture: And Logic Begat Computer Science: When Giants Roamed the Earth (I am not aware of a written version) https://www.youtube.com/watch?v=pMAT3B13DXs
I’m a bit hesitant to add wide-audience talks (as valuable as they are) in the body of the post, just because there are so many of those. But the comment section could be a great place to add more talks that people liked.
A.K Dewdney’s “The (New) Turing Omnibus” is nice introduction to interesting TCS problems of the sort that is great for the motivated high-school student.
James Gleick’s “The Information: A History, a Theory, a Flood”
Stephen Levy’s “Crypto: How the Code Rebels Beat the Government—Saving Privacy in the Digital Age”