RPG Chess! It's so simple, I can't be the first one to think of it. The game is basically chess with two small differences.
First, basic pieces level up when they take other pieces. Leveling up grants them new "powers" (pawns can start moving backward, for example). These powers are specific to the game they're in - they don't carry over to new games.
Second, there is a single new piece - tentatively titled the War Mage - whose leveling up does persist between games. The player gets one of these pieces per game which he can swap in for any pawn which has not moved. The War Mage's experience increases after completing a game, not after taking a piece. At its core, the War Mage moves like a king, but takes on other properties as it levels up.
The intent here is to add a new twist on Chess while keeping its "fairness" - every player still has the same exact opportunities, and there's no randomness.
There are still a few open questions:
Do pieces level up individually or as a group? That is, when a pawn takes a piece, does only that pawn level up or do all pawns level up? The former attempts to prevent a "runaway leader" problem, whereas the latter is easier to convey to the player. I feel like the former would be the better solution.
How do we illustrate the War Mage's abilities? If a War Mage has leveled up five times, it becomes cumbersome for the other player to remember what he's capable of doing. The new abilities could stem from a predictable path (ie: the War Mage can move an extra space for every level), but that seems like an underutilization. We could keep a reasonable upper limit on the number of different abilities at any given time (say, 3), which is probably reasonable.
I see this as a free, asynchronous iOS game with IAP for purchasing different War Mage avatars, board backgrounds, piece sets, or even board layouts. I thought of it as a simple game, but the more I sketch it out on paper, the more I see the complexity (mostly in terms of menus) increase.
A "nice to have" system I roughed out was a "Mission" system that would grant the player extra War Mage Experience and/or premium currency for performing certain tasks - winnings 5 games, getting a stalemate, upgrading a pawn, etc. Think Jetpack Joyride's Missions, Tiny Wings's nest upgrades, or the Cuddle Bears multiplier system. It's a little bonus I fell in love with in Tiny Wings, but obviously it's part of a wishlist and not part of the core feature set.
Don't know if I'll make this happen. I think there's merit in the idea, but who knows?