Robespierre was the natural consequence of the efforts of the Revolution to dechristianize France. The Terror was far worse than previous examples of "fanaticism" in either French or European history generally. As Burke observed, when you try to divorce a nation from its history the result is an inorganic and murderous regime. Any regime which attempts to construct a new society ex nihilo will murder on a massive scale. Non-belief is not usually neutral and harmless.
The Revolution and Reign of Terror were not examples of non-belief : they had their own ideology and, in Robespierre's cult of the Supreme Being, their own religion. The absence of Christian or Catholic belief may not necessarily be harmless, but the absence of any supernatural belief or hardline ideology almost certainly is. "There's nothing out there" or "Let's vote on it" are not the stuff to inspire genocide.
The Terror was not far worse than anything which preceded it. In France, more people were slaughtered in the St.Bartholomew's Day massacre than in the entire Reign of Terror. The Albigensian Crusade's fatality rate may also have exceeded that of The Terror.
Voids must be filled and in the case of modern Revolutions descended from the French one of 1789, the ideological "fill" has sent tens of millions of innocent souls to their deaths. In a very real sense, Bolshevism was an Atheistic crusade from the beginning, not simply in its Stalinist variant, which was fanatical, intolerant, and addicted to butchery on a scale previously unseen in the history of Christendom.
The scale of the butchery has more to do with the possession of the means and power to inflict it than with an unwillingness to take too many human lives. At the seige of Béziers in 1209, would Bishop Arnaud-Ameury have said "20,000 people? That's OK - kill them all" but "200,000 people? No, that's terrible!"? I don't think so. He had 100% of the townspeople slaughtered, fellow Catholics as well as opposition Cathars (because "God will look after his own"). It doesn't get worse than that.
While the Bolshevist crusade was atheistic, it was not an Atheist crusade; by which I mean that the promotion of non-belief in a diety was not its primary motivation. The motivation - the reason d'etre - of the Russian Revolution was the imposition of Communist ideology and power, of which atheism was a relatively minor element.
Western Europe and the United States have been spared much of this because they held to milder forms of the Enlightenment which did stress tolerance, but more importantly, they held to the core values of western civilization as inherited from both its classical and Christian roots. To condemn merely words such as "fundamentalism" or "fanaticism" is to do a disservice intellectually. It is to suggests all ideas, beliefs, traditions, and regimes are essentially the same and only tend to be troublesome when they take themselves too seriously and harm others.
I don't think it suggests that at all. It suggests that almost any idea or belief is dangerous when taken to the extreme of being regarded as an absolute truth which can be enforced without regard to others' rights and views. It says nothing about the relative merits of ideas and beliefs which don't go that far, and of which we can still approve or disapprove.
Europe's relativism will be its undoing in the current struggles of this century. What is needed is for the Western world to rediscover its roots and beliefs, thus itself, and not to seek simply to accomodate and tame others. We are what we believe, and this makes the position of the agnostic or atheist rather difficult.
The western world has many roots and beliefs : Christian, Pagan, Enlightenment, Democratic, Feudal etc … none are, or ever have been, immutable. The changes in knowledge, understanding and population mix make turning the clock back impossible; and to attempt to assert one set of beliefs as the norm will only polarize things and increase conflict.
I don't see why things should be particularly difficult for the atheist or agnostic. An atheist can have very clear views and principles, which are also heavily grounded in European and classical traditions, but don't happen to include a diety.