Books not already mentioned that fit all the characteristics listed except the second include, in no particular order:
- Walter M. Miller, Jr. - A Canticle for Leibowitz
- Isaac Asimov - Foundation Trilogy
- Ursula K. Le Guin - Hainish cycle (particularly The Left Hand of Darkness and The Dispossessed)
- Anything by China Miéville (some of these probably fit the second criterion too)
- Kurt Vonnegut - Cat's Cradle; The Sirens of Titan; Slaughterhouse-Five; Breakfast of Champions
- Philip K. Dick - Do Androids Dream of Electric Sheep?; Flow My Tears, the Policeman Said; The Man in the High Castle; probably a bunch of other novels as well
- Kim Stanley Robinson - Red Mars trilogy
- Iain M. Banks - Culture series
- Roger Zelazny - The Chronicles of Amber
- Terry Pratchett - Discworld series (Small Gods is the best starting place; Guards! Guards and Going Postal also aren't bad starting places)
- Jasper Fforde - Thursday Next series
That seems like a fair kickoff selection.
ETA: How could I forget Neil Gaiman's American Gods? I should've known I was leaving out something important.