and we have killed him..
What impresses me most about Nietzsche is how frighteningly prescient some of his writings were. For instance, an aphorism such as the following anticipates the enormity of totalitarianism by at least fifty years;
The better established the state is, the fainter is humanity (1873 Note, published in 'The Portable Nietzsche')
Additionally, his writings of changing value-systems, (The world revolves inaudibly-Thus Spoke Zarathustra) moral relativism, and subjectivity were of great influence to philosophers such as Foucault, which is presumably why Nietzsche has been dubbed 'The first postmodernist'., I think the following quote demonstrates this aspect nicely;
What, then, is truth? A mobile army of metaphors, metonyms and anthropomorphisms- in short, a sum of human relations, which have been enhanced, transposed, and embellished poetically and rhetorically, and which after long use seem firm, canonical and obligatory to a people; truths are illusions about which one has forgotten that this is what they are ('On Truth and Lie in an Extra-Moral Sense' pp.46-7)
I'd second the 'Portable Nietzsche' recommendation. Cheap, with Zarathustra, Twilight of the Idols, The Antichrist and Nietzsche contra Wagner published in their entirety, as well as another 150 pages of excerpts from other works, notes (Including that would eventually become posthumously compiled as 'The Will The Power') etc:. Well worth it.
For Plato, 'The Republic' is quite good, and a vital text in Classical philosophy. Also the first literary utopia...