The situation where Jesus was preaching was experiencing a decline in the authority of religion as well, in large part because of improved communication technology (That whole post office thing. Sure, it was old news in the core of the Empire, but out in the boonies...) bringing other religious ideas.
The Roman occupation also challenged the rather concrete view of the place of faith. Good was supposed to prosper and evil fail, except for the occasional test, and that was supposed to happen for the most part in this life. And here are these polytheistic Roman occupation forces getting all the goodies while faithful Jews get zilch if they are lucky. So is polytheism good, or Yahweh weak, or did we do something wrong, or what?
I'm not real convinced that things have changed much where it counts. Most people, for most of time, have been aware that there are others with other beleifs. Sure, we have access to more details about exactly what those are, but if you were curious you could almost always go to the next valley and find out. The situation in Europe in the middle ages, with one extremely dominant religion covering pretty much the entire known world, was a bit unusual. There have always been slimy zealots and good people that bad things happen to. People are born, learn that the world beyond Dad's house is scary, learn to deal with that, scrape together their daily bread, eat said bread preferably with friends and family, have sex and realize that there is something quite disturbing about the way the quest for sex transcends reasonable thought and prudence, get sick, die. And worry about all of it, try to fit it into the big story.
I am no smarter than the guys who painted those cave walls 20,000 years ago. And except for ultimately not particulary important details about tools and toys and precise modalities, I'm looking for the same things, doing the same things, worried about the same things. I may not have to worry about predators much, but it never was predators that worried people, but the sudden violent death predators bring. Sudden violent death hasn't gone away. And while it isn't likely that famine will strike my family, I worry about keeping them fed in bad years anyway.