Well, Nietzche is basically required reading if you want to discuss philosophy, especially with an historical leaning like your original post had. Of course, that never stopped anyone from jumping right in, so what can you do?
I'm not going to write a summary of the book, but I'll link you to
this brief summary. It does a decent job of summarizing, although I think it deemphasizes the historical nature of the work, in favor of the ethical stuff. "Geneology of Morals" is not the only Nietzche that addresses this topic. I cite it because it is the most comprehensive. I'm sure you've heard the "God is dead" quote countless times out of context. Here is the full quote, from "The Gay Science":
"God is dead; but given the way of men, there may still be caves for thousands of years in which his shadow will be shown. —And we—we still have to vanquish his shadow, too."
This is the anguish of the nonbelievers that you're looking for.