I think I can help answer this. I'll start with a reading recommendation, Richard J Evans "The Coming of the Third Reich". This is the text we used in college and was pretty thorough. It's also what I'll reference since it's the one I have available.
This is answering the question, were the Nazi's just viewed as another party in the beginning. The question of when the world knew they were evil will need its own part, which hopefully I can also provide shortly.
The Nazi party had its roots in the German Workers' Party. In the early 1920's this was just one of a number of small radical right parties in the Weimar republic, feeding off the instability and economic issues of post WWI Germany. This party became the National Socialist party by about 1921, and was nicknamed the Nazi's at that point. At this point their rhetoric was mainly anti-socialist, but the roots of their rabid antisemitism were there. They engaged in some brawls and minor rioting as early as 1921, and Hitler was even threatened with deportation (Evans, p. 181) (Sorry I haven't done references in a few years...).
This escalated to the point where the party was banned in a number of states in 1922, with the exception of Bavaria. There still isn't any indication they were viewed as more than right wing radicals even at this point however, and their real threat was probably not seen by most until we get closer to the Beer Hall Putsch.
In 1923, the Bavarian government appointed a commissioner to keep order, as they were concerned about the nationalists (principally the Nazi's). He proceeded to begin banning public meetings scheduled by the party. The tension culminated in November, when the Beer Hall Putsch (an assault by the Nazi party against the Bavarian state government) was executed. The Putsch failed, but this is probably the point that some Germans would have been concerned. It's important to note a few things. First, these events still did not garner much international attention beyond Germany, as far as I am aware, and second, the concerns were about the threat to order, not their antisemitism. Antisemitism was rampant in Germany and in Europe as a whole at this point, and there is a massive amount of history and information behind that. The antisemitism would not be a concern until later.
We can probably jump ahead here. After the Putsch, the party was declared illegal, and was banned until 1925. As late as 1928, they still only garnered about 2% of the vote in the Reichstag elections. This started changing in 1931 as a result of the onset of the Great Depression. During the period from 1925-1931, the Nazi's put a lot of effort into rebranding themselves and refining their propaganda techniques. Again according to Evans, the Nazi's started to be viewed as a viable alternative at this point, with people forgiving or forgetting how violent they were. It's important to note that the Nazi's were presenting a "viable" scapegoat and solution to the countries issues. We see this as evil through the perspective of history, but a growing number of desperate Germans seemed to see an opportunity for change and better fortunes. So while there was still suspicion of the party from many, the Nazi's still were not viewed as evil in Germany, and were still not an international concern.
I'm going to jump ahead here to the Reichstag Fire in Feb. 1933. In brief, A terrorist set fire to the Reichstag and Hitler blamed it on a Communist conspiracy, simultaneously presenting them as the enemy and the Nazi's as the heroes. He then suspended a number of civil liberties, including freedom of the press, expression, and privacy. Due to an effective propaganda campaign, this was fairly successful and had support from the German people. So the Nazi's again gained more power without being perceived as wholly evil.
The Reichstag fire and fallout were really the end of the Weimar Republic and the conception of the Third Reich. With the suppression of the communists that followed and a massive propaganda campaign, the Nazis are popular at this point, and their violent climb to power is overshadowed by and blamed on the Communists.
Summary: The inception of the Nazi's was as just one of a number of small, radical but nearly irrelevant right wing nationalist parties. Through their violent strategy and rhetoric, they were temporarily banned and unpopular for a number of years. A combination of global economic crises and propaganda allowed them to regain power and end civil freedom, while simultaneously staying popular enough to hold power.
Again, definitely read Evans book if you're interested in the topic. I found it very thorough. I believe that the rest of your question might be answered in Victor Klemperer's "I will bear witness", but I need to review a little before I can answer it.
I hope this helps answer your question.
Edit:
While Klemperer is definitely a book I would recommend and you could glean your answer there to some extent, it's not the text I was thinking of. I seem to have misplaced my other books after moving, so I can't give a thorough answer to the rest of your question right now as I had hoped. I will say that some key events that would have/should have warned the world are Krystalnacht, the annexation of the Sudetenland, and the annexation of Austria. As far as knowledge of the holocaust, this dribbled out in bits and pieces and was known of at a high level internationally, but the average person didn't learn much about it until the liberation of the camps. That subject deserves a more thorough explanation than I can do from memory however, so hopefully someone else can contribute to it.