If you think you'll manage reading Nietzsche himself, I would certainly recommend it - it'll give you a very direct image of his philosophy. I personally started with Beyond Good and Evil, and would recommend it as one of the first things you read; you will get right into Nietzsche's epistemology, his concept of will to power, and some fairly amusing attacks on other groups of thought (especially when he calls democrats sheep; I'll never forget that).
However, having read On the Genealogy of Morals later on, I would caution against starting immediately with Beyond Good and Evil, and instead recommend reading at least the first essay, if not the second of Nietzsche's Genealogy of Morals. This is why:
It has long been clear what my aim [in writing On the Genealogy of Morals] is, what the aim of that dangerous slogan is that is inscribed at the head of my last book Beyond Good and Evil. - At least this does not mean "Beyond Good and Bad." - [Genealogy of Morals, first essay, section 17]
So, reading those first two essays should give you a lot of insight into what you later read in Beyond Good and Evil, and give you a little taste of Nietzsche's general philosophy.
Once you read Beyond Good and Evil, I think Thus Spake Zarathustra might be an appropriate direction to head in, although the book itself can get pretty climactic and heavy. It may be better if you read a few of his other works (e.g. The Gay Science, a useful introduction to a few important concepts) before.
On a side note, if you're looking for something more along the lines of an autobiography (and also excellent literature), Ecce Homo is great, and regardless of what order you choose to read Nietzsche, this has to be pretty high on your list.