I think mythical fantasy and magitech will be a really strong concept. Maybe go for something ancient history focused?
An idea I had was it could be proper polytheism, where there is a god for absolutely everything. There would be gods of overarching concepts, like war and love and all that, but there would also be multitudes of gods of various things, like individual rocks and trees and rivers. (I'm basically ripping off from Shinto here, though ancient Western religions did a lot of this sort of thing, too.)
And so, if humans ever wanted anything, they would pray and make offerings to the specific god involved, and if the offering was acceptable and/or shaman making the request was personable enough, the god might deem to grant their request. A good shaman could generally get a god to take any reasonable request and could sometimes obtain more potent effects, but proper shamans were only those rare people who possessed the gift for such and had spent years honing their skill. If you were not such a person, you needed to know one to get magic done.
That is, until humans figured out how to trap gods in machines. Suddenly, you could have the power of a minor deity on tap. The nature of the god machines is such that they could only produce a certain kind of effect without moving the god to a new machine, so they're less flexible than the effects produced by a shaman, but, still, this meant you could have magic without needing to be or know a shaman.
Of course, the other gods and the shamans don't take too kindly to this sort of thing. Generally, the makers and users of god machines will either convince people to drive out shamans from a place or operate in secret, since the shamans strongly oppose them on moral grounds and out of fear that fraternizing with such people will harm their reputation with the gods. This isn't the case with all shamans, since there is no overarching body which governs them all (though there are certainly many national and international shaman organizations), and they are free to make up their own minds about matters, though most shamans tolerant of god machines will at least advocate for godly welfare.