The association between Nietzsche and the Nazis is mostly due to the actions of his sister, who was a hardcore National Socialist. She deliberately manipulated his letters and work in order to make him look rabidly anti-semitic. It seems the Nazis, including Hitler, had a superficial reading of Nietzsche. They interpreted his idea of a 'Superman' as some sort of Aryan ideal, while most agree that he meant something more akin to a Renaissance man or fully realized individual. He was quite critical of anti-semitism and German pride in some of his work.
Highdose, the brothers that freaked out on you truly had a reason to fear Nietzsche. It was reading his work as a teenager that gave me motivation to break free of the Witnesses once and for all. His ideas are delightfully dangerous to conventional thinking, he was a philosophical sledgehammer.
Nietzsche was not the first to criticize religion and God. What he was addressing when saying 'God is Dead' was what he saw as a great spiritual crisis that was coming, because God was no longer relevant to modern life. In his view, Christianity expoused weak values anyway, and had run its course ("The last Christian died on the cross" is one of his great quotes). In Nietzsche's evaluation, man (and he is gender specific, Nietzsche was a bit of a sexist) had to reevaluate his morals. To him, values were to be defined by vitality, power and living life to the fullest. In this sense I see Nietzsche as a optimistic, life-affirming philosopher.
Nietzsche is fun to read compared to some other philosophy, which can be dry at times. He is very poetic, which is why he is the favorite of artists. He is also very arrogant, opinionated, witty, and even contradictory, which is why he is also a favorite of many angst-ridden adolescents.
