They were bothered by a universe that is not based on comprehensible rules, but rather on the whims of things more powerful than us. Lovecraft at least, Lewis seems to have developed Stockholm Syndrome when he thought about it long enough.
And that is terrifying. Even if we are totally insignificant, if we exist in the context of universal, impersonal, and ultimately comprehensible laws of nature, then we can at least make methods to navigate and manipulate this universe. We may be far behind another species understanding, but we're working from the same rulebook. If, however, the rules we are capable of accessing and understanding, the very laws of nature themselves, are local, temporary, and subject to review, just not by us, then it is pretty terrifying. That's what you see in Lovecraft. People who discover this is so, and suddenly they start to see the edges of this everywhere.