I'd make the Deity of Medieval some kind of religious order for the Crusaders, for instance the Temple Knights, which did exist. Possibly we could also have some Muslim ordery, (not Allah or Mohammed directly, since that might offend real Muslims), but something historic, maybe Follower of Saladdin. And possibly you could worship the devil too.
You could also choose to follow any of the existing Barons and Knights as a Squire, (like Arthur, Lancelot, Galahad or the Robber Baron).
In Pre, we could just use the existing Greek and Egypt Gods - all of them already have their temples and properties, so that would be an easy adaption. There are both good and bad deities to choose from, but most of them were a bit... ambiguous.
Old West, hmm... I think Cthulhu is a 19th century goth fantasy, if you want to go for evil. Or maybe Dracula or Mirkheim, for vampires.
The 'good' ones could just be common, god-fearing Republicans and follow the local preacher. :-P
Otherwise the deputy/sheriff, versus outlaws idea works fine for me. You could for instance follow the Wild Bunch in Hole in the Wall, or any of the existing marshals. (i actually had a quest for this planned in the past, that I never got around to implement.
And wasn't the Indian deity called Manitou?
Future I am not so sure about. Jedi and Dark Jedi would have the been natural choice, if we hadn't already got the DJ Clan.
We could of course invent some obscure local deities for various planets. The only one I know of so far is Herbie, on Yudore. I'd rather like him as a deity, he's a funny guy.
Or you could follow the Robert Young Space Cadets, I already have a quest for that in the making for other things. Then there could be a band of Space bandits, for the evil.