A few possible settings:
-A setting based on American Indian culture/mythos (more present-day US/Canada, rather than Meso-American like Maztica). This could go hand-in-hand with the spirits being more manifest suggestion earlier. Perhaps add some very early contact with other societies (Celtic-like people across the frozen Atlantic, Vikings, Siberians across the strait, maybe even east Asian/Chinese type connection)
-Settings that defy the basic assumptions of 4E (Fantastic Place, Ancient, Mysterious, Races Banded Together, Distant gods, etc). For example, a world that the PCs are part of an early expedition into a brand new world, or one where the PCs (and some important NPCs) are the only magic-wielders (maybe magic is a new phenomenon that hadn't existed before), or maybe one where the PC races are hostile to each other.
-Frontier World: PCs are from a distant, civilized land/world, exploring an alien environment. This could either be a new continent, like the real-world Age of Exploration, or a new world/plane of existence.
-Fantasy Old West setting. Cowboys, Indians, Orcs, and Wizards!
-Multi-world setting: Like, say, the Death Gate Cycle, Stargate, Sliders, etc. Some series of portals or such connects these worlds, and many of the various races could be natives to different worlds, with vastly different cultures, architecture, and living in different environments.
-Immortals-based/Super-Hero setting. This could combine traditional D&D with the mutations/powers of Gamma World. The PCs (major NPCs and Villains, too) aren't just exceptional as adventurers, but they are inherently super-human/elf/dwarf/etc. In traditional fantasy, they could be agents of the gods posing as the mortal races. In more historical/gritty/sword-and-sorcery settings, they could be demi-gods (like in Greek mythology). In more modern settings, super heroes. The like.
-Finally, a setting where one or more traditional races are gone (extinct/never existed), radically different (giant dwarf-like race, techie elves, etc.), or hero/villain swapped (good orcs, evil elves, or the like). Athas does have this.