I would recommend starting out with The Gay Science translated by Walter Kaufmann. A good translation (and footnotes, which Kaufmann provides) is invaluable in connecting the dots of Nietzsche's thoughts into a coherent web of ideas.

N had an uncanny knack for getting to the root of our beliefs and values through observation and introspection, and he gave voice to his ideas in profoundly creative and inventive writing. Though a monolingual English speaker myself, I've heard that he is almost the Shakespeare of the German language along with Goethe.