Most articles related to this topic suggest something like the Fight Club. Even though, there are some good twists to the story, I feel like my mind could be blown away way more than that.
Needless to say that we are talking about a book for the HN audience.
Le ton beau de Marot, also by Douglas Hofstadter. Was blown by his description of how making the typographical choice of starting the first word of each chapter with letters decreasing in height to the normal page font size, caused him to rethink a whole chapter (he couldn't use descenders, which limits the first word, which limits his first sentence, which constrains his first paragraph and so on).
Harry Potter and the Methods of Rationality, by Eliezer Yudkowsky. Every single chapter is potentially mind blowing. The whole approach of trying to instruct rationality through such fiction is itself brilliant I think.
The idea that organisms evolved to be survival vehicles for our genes totally inverted and simplified my view of life. It gave me a plausible explanation for how we came to be, and put the final nail in religion's coffin (for me).
The book is a mind-boggling journey through our own evolutionary history and delivers surprising and sometimes funny insights on many aspects of our behavior as modern humans (e.g. it attempts to explain the origins of religion, dancing and music). The beauty of the book lies in the fact that it makes you understand in detail which processes have transformed us from primates to modern humans. Truly fascinating, beautiful stuff.
Most people probably know Dunbar from "Dunbar's number", which relates the relative brain size of animals to the number of individuals with which they live together (http://en.wikipedia.org/wiki/Dunbar%27s_number). This often (mis-)cited number is but one example of Dunbar's ingenious, math-driven approach to many problems in biology and evolution.
To maximize mind-blowing capacity, combine Dunbar with Jared Diamond's "The World Until Yesterday" (http://en.wikipedia.org/wiki/The_World_Until_Yesterday), which explains how our ancestors and many traditional tribes lived (and sometimes still live), and "The Selfish Gene" by Richard Dawkins (http://en.wikipedia.org/wiki/The_Selfish_Gene), which explains many aspects of life and social organization using mathematics and evolution theory.
For me, this stuff is more mysterious, thrilling and captivating than any fiction book I've ever read.
One of these days I will buy all of Jared Diamond's and Robert Greene's books and read them multiple times.
For very different perspectives on programming, check out Structure and Interpretation of Computer Programming (read it a decade ago and I use techniques from there every day.)
The Gift by Lewis Hyde. Although directed at artists, it is highly relevant to creative programmers and the phenomenon of open source. He is able to articulate things which are very hard to talk about, like the intersection of economics and artistry, and how the gifting ethos is necessary for any culture to thrive. If you think ESR had the last word on how open source works, you need to read this.
Another book of interest by Hyde is Trickster Makes This World, wherein you learn the hacker archetype - the giver of technology; the player of tricks - has been around since prehistory. It's not a coincidence that those two aspects are always seen together.
also, not a book but very good "The last question" Isaac Asimov 
NOTE1: spoiler alert.
NOTE2: please don't think of me as some heartless Objectivist - I have adjusted my views since I read it about 10 years ago but at the time, the following points were earth-shaking revelations to me:
* It revealed to me how influence peddlers in society use a combination of coercion and guilt to suppress an individual's individuality
* It revealed that these "thugs" are interested in suppressing your thoughts and controlling your money. I read this book during the Bush years and the suppression of speech in the name of "patriotism" rang true, while prior regimes' punitive taxation policies also rang true as meeting Rand's definition of thugs.
* She basically posits that an individual's greatest purpose of existence is to create and to do the best for themselves that they can.
Within the above kernels, which with moderation I feel are very powerful insights, are interspersed a lot of distractions. Her writing style is retch-inducing and her hatred of native people in continents that were abused by colonialism is bafflingly naive. My edition of the book had about 1100 pages, 100 or so of which were Galt's long speech - it was an endeavor to finish this book but I am happy to have learnt the above insights.
How would that behaviour be rationalised from Foutainhead?
It did so by presenting a fictional instance of unjust economic laws. At least I read it as pure fiction - whether such unjust laws actually exist anywhere in the world is, I think, best treated as a completely separate question.
It gave me a new respect for entrepreneurs.
There's also the Imperial Radch series which is a very, very good sci fi series which is unlike any other sf I've ever read.
>Winner of the Hugo, Nebula, British Science Fiction, Locus and Arthur C. Clarke Awards.
The Moral Animal, Robert Wright. It looks at how natural selection applies to human cultures.
Debt: The First 5,000 Years, David Graeber. History of economic systems. Everything we know about money is one of many alternatives tried somewhere at some time.
Where Mathematics Comes From, George Lakoff. Presents the radical notion that math is not a truth we've discovered, but a byproduct of the organization of our brains. It looks at the evolution of the concept of infinity as an example, and so it resembles David Foster Wallace's Infinity and More.
I think these books all have the theme that what we think of as reality is just the current point on the random path of our culture's concensus. If that's not mind blowing, I can't help you. (-:
To Kill a Mockingbird, by Harper Lee. The timeless beauty and innocence of the book remains unparalleled.
Light in August, by William Faulkner. It is the opposite of the above, dealing with complex emotions. Faulkner's prose and characters are unmatched in their depth.
I've read these books midway through high school, already interested in biology and medicine. The depth and complexity of how life forms handle evolutionary pressure is mind blowing. Why you favor relatives over strangers, the competition between mother and child, progress through collaboration of genes etc. You see the world completely differently (after reading many more books on geology, genetics, anthropology, anatomy, cellular biology etc) afterwards.
For a novel: Cryptonomicon by Neal Stephenson,
Truely changed how I look at computers and encryption as a not mathematically inclined reader. Building a computer out of church pipe organ components etc.
"Thinking Fast and Slow" by Daniel Kahneman.
"Quantum Computing since Democritus" by Scott Aaronson.
"The Strategy of Conflict" by Thomas Schelling.
"Guns, Germs, and Steel" and "The World until Yesterday" by Jared Diamond.
"The Retreat To Commitment" by W. W. Bartley.
"The Myth of the Rational Voter" by Bryan Caplan. Despite the name it made me appreciate democracy a lot more.
"Wars, Guns, and Votes" by Paul Collier.
"Strategy: The Logic of War and Peace" by Edward N. Luttwak
For me it consistently produces one OMG or more per chapter.
This book advocates personal freedom from beliefs and agreements that we have made with ourselves and others that are creating limitation and unhappiness in our lives.
'The Spandrels of San Marco and the Panglossian Paradigm: A Critique of the Adaptationist Programme', SJ Gould and RC Lewontin
'The Origins of Genome Architecture', M Lynch
'Mutation-Driven Evolution', M Nei
”what Dawkins did was just giving it the catchy name”
Well, he also wrote an accessible book on the subject. And that book is littered with references to other literature on the subject.
Blowed my mind when I read the Chinese translation of this book 25 years ago in College.
A totally astounding introduction to how computing fits into the broader scale of understanding other phenomena in our everyday scientific lives — and, unlike most “oh wide-eyed wonder!” popsci books it contains code, equations, and deeply significant diagrams.
Have a lot of great memories of him and his daughter. Now that I have young kids of my own, every so often something reminds me of those days.
The Wisdom of Insecurity by Watts helped center my adolescence.
Not mind blowing in that there was any startling revelations in it, rather that reading and absorbing it changed my outlook on many things.
On a more spiritual note, I'd also recommend Mindsight by Dan Siegel . An excellent book for getting some intuition into how people's past experiences shape them. The Trauma of Everyday life by Mark Epstien  blends teachings of Buddhism and mindfulness with the life long lessons of a Psychotherapist.
- Borges, Ficciones (http://en.wikipedia.org/wiki/Ficciones); that's the quintessence of mind-blowing literature: an unparalleled mix of genius, culture and crazy imagination.
- Celine, Journey to the End of the Night; a harsh, hopeless journey to the bottom of humanity. It's not an easy read even though the style is so simple. Think Houellebecq, but much better :)
- Dostoyevsky; I was obsessed with him when I was younger. "Notes from the underground" is one of the best introductions to existential nihilism I can think of. "The Idiot" one of the few books that made me cry.
- The Marriage of Cadmus and Harmony; if you're into Greek literature, this book will become your Bible; it requires a lot of attention and dedication though, it's incredibly dense.
Set as a satire of Victorian society "The story describes a two-dimensional world occupied by geometric figures, whereof women are simple line-segments, while men are polygons with various numbers of sides. The narrator is a square named A Square, a member of the caste of gentlemen and professionals, who guides the readers through some of the implications of life in two dimensions."
I won't spoil this one for you, it's just a really interesting and suspenseful sf story.
Richard Dawkins (writing in the 2010 Penguin Classics reissue) claimed the novel was "one of the greatest science fiction novels ever written."
This changed how I look at my life
The line "I have an idea, a simple idea, based on the quite obvious fact that the number two is ridiculous and can't exist." has stayed with me for over a decade now as has the surprising lovemaking of the aliens.
For a hard read that you may enjoy I'd suggest "The Book of the New Sun". I'm re-reading it for the fourth time and it just gets better.
Kanefsky may be familiar to many HN readers for his song "Eternal Flame", about the superiority of Lisp to other languages, also sung by Julia Ecklar .
I found it on this list:
Where also the following books some of which I read to (Vehicles is really good) can be found:
The White Goddess - Robert Graves
Graves' grammar of poetic myth works at so many levels at the same time that I can't keep track of them all. This is not a book, this is a neurosis you can borrow. Druidic power to the nerds.
The Origin of Consciousness in the Breakdown of the Bicameral Mind - Julian Jaynes
Never mind the bulky title. The theory of Jaynes seems preposterous at first: before man was conscious he would not stop and think when making a decision, instead he would literally hear a voice telling him what to do. When life became too complicated this faculty broke down, but not in an instant. Religion is a by-product of this neuro-catastrophe. Jaynes however knows to make use of historic material in such a way that in the course of his argument he becomes plausible! If you don't trust me on this, trust Daniel Dennett.
The Ghost of Chance - William S. Burroughs
Burroughs was a great admirer of Jaynes and here he uses the bicameral image of two dividing brain spheres as a metaphor for the divide between peaceful lemur on Madagascar and the war-mongering chimpanzee on the African mainland as a reminder that human evolution could have taken a better turn.
Ancient Evenings - Norman Mailer
This book, the only lengthy novel in this list, I first looked up because Burroughs referenced it as his inspiration for 'The Western Lands'. When I noticed it starts with my favourite Yeats quote I knew I needed to read this. Even though Burroughs could never have written it like this, at times it is more Burroughs then Burroughs himself. It is the autobiography of a Ka, the lowliest soul of the seven souls of the ancient Egyptians, which makes for unusual reading. Especially because Mailer uses an uncensored version of Egyptian mythology which, to put it mildly, differs from the version you get of it from the National Geographic. The Egyptians practised sex magic with the stamina of a bonobo. Mailer makes Aleister Crowley look like a prudish schoolboy. This is the boldest attempt to recreate a radically different mind from ours that I know of, and does so successfully. The novel as the creation of an artificial consciousness. At the same time it doubles as an All American Novel (yuk).
The Mind in the Cave - David Lewis-Williams
Palaeolithic Psychedelia anyone? Close your eyes, place a finger on both of your eyelids and press gently. What you see is the origin of all art, you only need to look at rock-art with a guide like Lewis-Williams to see it.
The Chinese Written Character as a Medium for Poetry - Ernest Fennolosa
Edited by Ezra Pound, the most spectacular misunderstanding of language ever to be reprinted. It reads excellent and it gives us a language (Chinoiserie-Chinese) that does not exist in this world but should exist in a better world.
Vehicles - Valentino Braitenberg
I have read so much stuff relating to Cybernetics, AI, emergent systems and self-organization that I am totally saturated with it. The material itself is exciting but the professional obligation of science to be dull gets on my nerves. But this is an exception, wonderfully written and illustrated with funky little drawings. Vehicles is a tiny book but its size is deceptive. This introduction to synthetic psychology describes a number of simple responsive vehicles that with each new feature became aware of the world around them a good deal more. Each new vehicle is a new mind.
The Coleridge Notebooks.
Charles Lamb said he loved to lend his books to ‘Poet, Metaphysician, Bard’ Coleridge because he would return them with annotations more interesting then the book itself. Samuel Taylor Coleridge had a mind that was free, discursive, unruly and truly original. His notebooks record the flow of his thoughts as if you are sitting next to him. Every now and then I dip into this and always come out with some gem I never saw before. Get the Seamus Perry edition of this. Get a copy of the Road to Xanadu by Livingstone-Lowes for extra enjoyment.
Gödel, Escher, Bach - An Eternal Golden Braid, by Douglas Hofstadter. Anytime I start reading a story which contains recursiveness my mind will feel warped and stuck in a loop at times.
http://amzn.to/1KijebX (affiliate link)
http://www.amazon.com/gp/product/0465026567 (non affiliate link)
Flowers for Algernon, Daniel Keyes
Dune Series, Frank Herbert
Foundation Series, Isaac Asimov
Calculus Made Easy Paperback, Silvanus P. Thompson
Building on philosophical ideas from the Frankfurt school Taussig strings together ethnographic examples & historical vignettes to outline the human faculty for mimicry, and how it permeates everyday life.
It really has opened my eyes about how to deal with having a negative attitude and understanding the driving forces behind being in the "flow"
"Novum Organum" by Francis Bacon 
For fiction, Ted Chiang is my go-to author when I want my mind blown.
It made me think about mortality, love and sexuality in ways I'd never thought of before
Not that "crazy-to-grasp" approximates "good" in any way.
Listen Little Man - Wilhelm Reich
Praise to Hell - Gunduz Vassaf (actully I read this book in turkish and I don't know is it translated to english but I still want to recommend this one)
Grimwood's “Replay” is a great time travel novel if you're into that.
The Malazan Book of the Fallen (10 volumes) - Stephen Erikson - redefines impenetrable
Use of Weapons by Iain M Banks - master of the interwoven narrative
ℝ ≈ P(ℕ)
I've read it several times and each time I found something interesting that I didn't notice.
"Zen and the Art of Motorcycle Maintenance" by Robert M. Pirsing
Seconded. I think this one does a good job at resetting one's worldview to the state of 'what do we actually know?'
Opened my mind and put into writing some of the things I'd been contemplating.
"I Am That" by Nisargadatta Maharaj.
- Hermann Hesse - The Glass Bead Game
- Hofstädter - Gödel, Escher, Bach
- Bulgakov - Master and Margherita
- Melville - Moby Dick
- Joyce - Ulysses
- Everything by Baudrillard (esp. 'Agony of Power')
- Everything by William Burroughs (The ticket that exploded, Place of dead roads, Discipline of DE)
Not that crazy to grasp, but still amazing:
- Everything by Egon Friedell (mostly Historical, unbelievably dense and awesome)
- Chatwin - Songlines
- Ludwig Marcuse - Philosophy of Happiness / Philosophy of Unhappiness
I like the Hesse book a lot, although the metaphor is more powerful to me than the book, which is probably not the first Hesse book I'd suggest.
And truth to what you say about the glass bead game, the first 200 pages are a torture, but I still cherish it even for the metaphor alone. Do you know of any book that does a better job bringing that across? That'd be very interesting.
+ Edit to my post: Meant to put Finnegan's wake to Joyce, not Ulysses! (even thought that's a pretty decent mindbender in itself)
+ Some I forgot:
- C G Jung - The Red Book (get the readers edition)
- Nobody mentioned McKenna! 'True Hallucinations' for example. Skip everything to do with I Ching and Timewave.
- Illuminatus! trilogy was only mentioned once for some reason (but then horrible to read)
- Toffler - Third Wave
- Gibson - Neuromancer
- Hesse - Demian
- P K Dick - Electric Sheep
- J A West - Serpent in the sky
- R A Wilson - Prometheus Rising
and some awesomely trippy, mindbending 'children's books':
- Preußler - Krabat
- Lindgreen - Brothers Lionheart
- Ende - Momo
We're all playing a game and most of us aren't even aware that we can choose not to play. Yossarian is one of the bravest characters in all of literature. He stays true to himself even in the face of overwhelming evidence that all of the world disagrees with him.