Hafta agree with quite a few folks on this one--the classics are the way to go. Keep their vitality & freshness despite the passage of time.
Leiber's Fafhrd & Grey Mouser works are a good example of a unique fantasy/sword-&-sorcery setting. Many of the characters & its foes are human, but the there are some interesting non-human characters in the setting: the sentient Rats of Lankhmar Below; the crystal-fleshed cannibalistic Ghouls; the wierd & alien wizards Sheelba of the Eyeless Face & Ningauble of the Seven Eyes; the scaled, sinister Simorgyans; the Ice Gnomes; the alien Devourers; and the Invisibles of Stardock.
It also has a unique twist in other elements as well: the continually rising & falling land bridge known as the Sinking Land; Ningauble's Caves (which link between dimensions/realities); the Shadowland (an actual realm of the dead on the world, where Death & his victims reside); and the underground rat metropolis of Lankhmar Below.
The setting is typical of an earlier age, but it's unclear whether if it's medieval, dark ages, renaissance, iron age, or some weird mix of all of the above. Viking-like Northerners and Mongol-like Mingols rub shoulders with courtesans and rapier-wielding bravos in the decadent, Rome-like city of Lankhmar. Pretty interesting stuff.
LeGuin's Earthsea works are a unique twist to fantasy, as well. The world is dominated by water, with only a cluster of islands available for the human populace to dwell on. It is more of an earlier age (closer to a Bronze Age or Iron Age setting than anything else), and magic, in its essence, is the knowledge of words of power & true names, and the power that having/using those terms have on the world around you.
For some somewhat newer fare, the Thieves' World anthology is another interesting setting. It's human-dominant as well, but focuses on life in a single city. The occassional non-human/semi-human races are encountered (like the winged creatures in 1 short story; or the aquatic Beysibs), but it's all about life & death in Sanctuary. However, as the stories/books progress, the power level is multiplied significantly (& it messes up the city severely). At the end of the first series, the city's been conquered, divided by warring factions, & faced visits/annihilation from various deities.
Though comedic, Asprin's Myth Adventures series is something different, as well: demons are basically dimensional travellers who visit other worlds--many monsters (like devils & trolls) are merely residents from other realities. It's a more magic-heavy setting, but magic is the key thing which makes dimensional travel feasible.
And, I haven't even mentioned stuff like Elric of Melnibone, the Welsh myth-inspired Prydain Chronicles, the pre-historic Earth of Conan, or other works.
I think that "freshness" is not necessarily inventing something new from wholecloth & using it, but can be just using existing ideas and concepts from a different perspective. Asprin's Myth Adventures does this by turning monsters from strange beasts into extradimensional travellers/merchants/vacationers. Both Howard & Leiber use a mish-mash of familiar elements and weird inventions to create unique worlds of their own.
And, despite the characters & the settings, the basic themes of the stories remain the same; grim-&-gritty adventure; an epic quest; a journey of self-discovery; a tale of love and romance; exploration of the unknown; a chronicle of aspirations and struggles for power; a tale of revenge; the solving of a mystery/problem; etc.
