I haven't seen it mentioned yet: Metamagical Themas by Douglas Hofstadter - this book was a game changer for me - I read it in college over a partiularly rainy spring break and its content has changed the way I think about just about everything.

Systems Thinking: A Primer by Donella Meadows is also an incredibly thought-provoking non-fiction book, that really makes you think about the world and the systems we create differently.