AppetizersA Tunes Learning Lounge course.
The Unknowable by Gregory Chaitin. An online book about Gödel/Turing incompleteness, unprovability of elegance of (what happen to be Lisp-) expressions, algorithmic information theory and the quasi-empiricality of mathematics. Prerequisites: none; if you're completely new to these kinds of topics, it will serve the task of awakening your curiosity about reflection, formal calculi, etc. Also very interesting for more advanced people (who might follow on with Li and Vitanyi's book on Kolmogorov Complexity).
Gödel, Escher, Bach and other works by Douglas Hofstadter are full of wit and poetry, by someone who dreams of AI, but paradoxically shows how high the stakes are to achieve it. Not all that insightful for understanding actual computing, though - do not take it for what it isn't.
Metaconnaissance by Jacques Pitrat is a great book for those who can read french.