To answer the original question, for me it seems not so much doing things differently as in "no elves, dwarves, or gnomes" or something like "magic is magic, no divine/arcane split," but changing how the different elements work in the game.
For instance, let's take races. I emphasize races moreso than other elements because it is one of the central aspects of actual play (as opposed to just reading) because it forms (or should form) the main aspect of a character's identity. If it doesn't, then the existence of different races is meaningless (except, maybe, for the case of certain classes like paladins and druids).
Consider the treatment of elves in various settings. I like elves. I'm deeply infatuated with elves. I like the idea of a class of beings so similar to humanity but with 2 major differences: magic and immortality (well, sorta). But I get tired of seeing so many settings rehash the same tired old elf cliches. It seems that the only way people seem to know how to create substantial differences between races is to create subraces. I wouldn't mind this if there were cultural, linguistic, and ideological differences to go along with them, to at least show potential seeds of conflict. But, no. In virtually every setting that features elves, they share the same lifestyles, beliefs, interests, and attitudes; their differences between are cosmetic and mechanical rather than cultural. I concur with
this guy when he says, "(The) more ethnic groups you create within your race, the more interesting (and believable) the race will become as a whole. Think how many ethnic groups there are within our own race. Why should fantasy races be any different?" As much as I'd like to see fantasy RPGs move away from Tolkien, this is one element of Tolkien's works that I'd like to see more of: even within so-called races, language and culture creates great diversity.
I think it comes more from not knowing what elves (or any race) are in the context of the setting than anything else. Oftentimes I see settings just describe different aspects of the setting, not really going into any detail about the role it plays in the greater scheme of things. Once again, I hearken to Tolkien. As much as fantasy novels and games are influenced by him, this is one thing I wish they were more careful about. One thing I like about Middle Earth is that, even without Tolkien directly stating it, I saw that each of the Free Peoples had a role unique to them that was reflected in their psychology, attitudes and abilities. However, in many RPG products, you don't get this. At most, you get likes and dislikes and a few attitudes, but no sense of where they come from or why it matters. Usually, these read more like instructions on how an individual player should play an individual character "correctly." You get no sense of what makes an elf and elf, or a dwarf a dwarf, or a gnome a gnome, etc, in any game. You just get . . . data. Without that thematic grounding, the most you can do is play by a bunch of details that don't mean anything to the player in the context of the setting. I can understand why people so often see elves as "humans with pointed ears."
Now let's examine the worlds. Once again, I don't think the problem is medieval fantasy, but doing the same type of medieval fantasy. The basic setup is often so predictable that as soon as you start reading, they jump out at you. You have a continent that is roughly similar to medievel Europe (at least, cosmetically), and the area is divided into a few nations, one of which is obviously the most powerful and influential culturally. Humans are dominant except for isolated enclaves in the forests (elves) or mountains (dwarves), although gnomes and halflings don't have a place to call their own, so they assimilate into human cultures. You have a history that presents a unified cosmology that opens with the creation of the world and describes in so many words how the world came to be what it was. Interestingly, there is no uncertainty, no mystery, no differences of opinion or focus. You often have a special class of people called adventurers, and this status trumps whatever cultural, national, or ideological differences they may have. Playing up these flavorful elements is usually more because of the DM's efforts than anything put forth in the setting.
What I consider different for a setting is creating different patterns or developing different ways to address certain elements. What about a game that centers around a cosmological question and different people's reactions to them? What about a game that addresses the idea of mankind by showing humans as the deviant rather than the norm? How about having cultures that are truly different, with different currency, different belief systems, different languages, and different social structures? Feudalism and monarchies are everywhere these days. How about some clans, tribes, matrilineal societies, democracy, theocracy, or even a meritocracy? The DMG presents a magocracy as a distinct possibility, yet I have never seen a world published that explores that idea. What about worlds that feature varying degrees of magic and technology for various cultures? In such a setting, what about elf cultures that embrace science and technology, and human cultures that embrace magic? Or, if you want to get radical, present a world that is medieval in its attitudes and beliefs as opposed to the fact that people wear chainmail and fight with swords and bows. There is a wealth of potential ideas and themes that can be explored more fully in settings, but rarely do they go beyond the formula.
I think what I'd like to see more than anything else is a new take on old ideas. Of course, I could try to do these myself, but who has the time, and who would be interested?