I know that's terribly vague but I can't narrow it down yet. Maybe a game that has a tighter focus and mechanics for the narrative instead of being centered on dungeon-bashing? Or on politics? A rules-light game? Genre-mix? Or a system using a campaign world that has a very unique spin?
Stormbringer (or
Basic Roleplaying with a swords-n-sorcery theme) is a little bit different without being "way different." Skills focused. Magic of the "sorcerer in league with demons" variety, rather than the "wizard throwing around fireballs" variety. Power points rather than memorized spells. Grittier tone than the typical D&D campaign. (I'm talking about the Chaosium 1e version; I'm not familiar with the others.)
Amber includes a lot of the possible differences you listed, and might work particularly well for the political aspect. It's diceless, so it's quite different from the typical D&D game.
In A Wicked Age is another one in the "very different" category. It's definitely a narrative-focused, collaborative "story game," not a "players explore the GM's world" game. However, dice are part of conflict resolution. Requires no prep (very cool "oracle" story/plot hooks with this one). Sessions can jump back and forth in time, and characters change often. Strong swords-n-sorcery focus (but there are other "oracles" online that allow for all sorts of settings and tone).
Cthulhu Dark Ages uses BRP, so it's not as far away from D&D, mechanically, but the theme, tone, and expectations for the game are very different. It's "Cthulhu by torchlight."
Trail of Cthulhu uses GUMSHOE, which is a nifty approach for investigative games. "Core clues" that are necessary to the story are always discoverable (never missed, as long as you look, so you'll never get "stuck" or require GM "second chances" and contortions because of a missed perception roll) -- the real challenge is interpreting the clues. Has two "lose it" concepts: one for Stability and one for Sanity. Overall, a lighter system than BRP, though.
The Dying Earth is a really cool game with a more narrative approach and some neat mechanics that fit the setting. And some *real* Vancian magic.
