Gödel makes everyone weep. For tears of joy, my top pick is still Doug Hofstadter's Gödel, Escher, Bach, which is suitable for undergraduates. Another strong classic is Raymond Smullyan's To Mock a Mockingbird. Both of these dead-trees are worth it; I personally find myself cracking them open regularly for citations, quotes, and insights. For tears of frustration, the best way to fully understand the numerical machinery is Peter Smith's An Introduction to Gödel's Theorems, freely available online. These books are still receiving new editions, but any edition should suffice. If the goal is merely to ensure that the student can diagonalize, then the student can directly read Bill Lawvere's 1968 paper Diagonal arguments & Cartesian closed categories with undergraduate category theory, but in any case they should also read Noson Yanofsky's 2003 expository paper A universal approach to self-referential paradoxes, incompleteness & fixed points. The easiest options are at the beginning of the paragraph and the hardest ones are at the end; nonetheless any option will cover Cantor, Russell, Gödel, Turing, Tarski, and the essentials of diagonalization.

I don't know what to do about stuff like the Complexity Zoo. Their veterinarian is Greg Kuberberg, a decent guy who draws lots of diagrams. I took some photos myself when I last visited. But obviously it's not an ideal situation for the best-known encyclopedia to be run by Aaronson and Habryka.