Diaspora by Greg Egan. No other book has caused such a seismic shift in how I think about consciousness, personhood, continuity of self, the enormity of the universe, and practicalities of galactic timescales. It also triggered quite a few existential crises (which nearly goes without saying, given all that).
I personally prefer Permutation City - for similar reasons. I don't think a book has quite affected my thoughts on what consciousness means quite as much as that book, and it's very interesting to boot.
