A game like Far Cry:Primal during the crusades before the unification of the UK(the amount of weapon variety and enemies showing up from all over to fight for one reason or another), 13th Century West Africa like Benin or Mali(the amount of tribes, ideas, architecture, style, and the issues between nomads and those that want to get into the slave game or strengthen their kingdom) hell even during the collapse of the Aztec Triple Alliance would be cool.
A Fallout style faction system would make the settings expansive as well as highly immersive. You know the action would be the GOAT. All settings have beautiful settings, high amounts of turmoil, space for perspective from multiple angles as well to room depict cruelty and bleakness of the world in those times.
Your character wouldn't be some out of place super killer who woke up one day an expert on dealing death and never faces consequence. The story may have more context and emotional weight. The sneak system would have a real place and there would be no shortage of weapons or reason.