As for the layman's journey I think the approach on Complexity of Gregory Chaitin in "Meta Math!: The Quest for Omega" may give you some ideas. Interesting read by an interesting person btw.
Other good books dealing with computational
complexity, mostly as it relates to AI
Douglas Hofstadter:
Gödel, Escher, Bach (classic!)
Rudy Rucker:
Infinity and the Mind (transfinite sets, Gödel's proof)
Rudy Rucker:
Mind Tools (complexity, Chaitin's Omega)
Roger Penrose:
Emperor's New Mind (Anti-AI: the first part of the book is
about the incompleteness theorems)