One setting I think never gets enough attention for fantasy is the brand-spanking new colony. The players are right off the ships. There is a small town and some docks. Go ten miles inland, and it's largely unmapped wilderness filled with savages.
This also allows the players to have a variety of backgrounds. Maybe
they came from a cosmopolitan Empire. Maybe it's just a bunch of
prisoners dumped off at a work camp (in preparation for the "real"
colonists). Maybe one of the players is a friendly native.
Another twist would be that the natives are goblins or elves, and the colonists are humans and dwarves and halflings. Or some other mix.
It would also be cool if the new territory had once been a powerful empire, but was wiped out for some reason. The current occupants are the barbaric remnants of this empire, and at least a few of their old cities lie in ruins not that far distant from the colonists.