The mechanics of the game fundamentally change how it is played, and what kind of flavor the game has. A lot of people seem to forget this, and they instead think about how to tweak the parameters of familiar mechanics to give the proper feel. For example, I've seen people try to run horror-themed D&D games, and I've seen people try to run lighthearted, slapstick Shadowrun games.
I've also seen this in computer games, where old techniques are recycled into a very different kind of game, and it doesn't usually end well. At least computer games have the excuse that making a new set of mechanics is actually difficult. There's no excuse for using the same mechanics over and over in tabletop games, unless your only point is to be as familiar as possible to the players.
There are a wide variety of relatively simple rule changes you might want to think about making to give your games different flavors. These are suggesting with tabletop games in mind, but they can be adapted to anything.
Replacing the Randomizer
Most new designers of tabletop games are happy to simply change the number of sides on the dice you roll. After all, rolling a bunch of d10s is quite different from rolling a bunch of d6s, right? And what if you have to roll a bunch of DIFFERENT kinds of dice? Whoa, it's like a breakthrough.
Well, you can make dice feel different, especially if you throw in exploding dice or pattern matching results (pairs are worth more, or rolling three sixes kills you, or whatever). Dice are also easy to calculate if you run that way: you can easily determine the precise chances of things happening if you know how many dice they have and what their target is.
But there are lots of ways to replace the randomizer. There are two basic categories: replacing the random function and offsetting the random function. Replacing the random function is just a matter of choosing a different method of randomization. Most are interchangeable with dice to a large extent, but some are not. For example, if you use cards, then the cards drawn from the deck cannot be redrawn, so it is possible to count the cards, modify which cards are put into the deck, and other things that "stack" the deck to your (or your players') preference.
My preferred method is to offset the randomizing function, by which I mean that the randomness is controlled by the players. For example, if the players are each given five cards that they look at and can play on any conflict, then it is up to the players to choose which cards they will use up when. Add in trading cards and character-specific pattern recognition, and trading cards becomes a major element of the game.
There are lots of other methods, such as allowing players to bid on dice, or spend points to reroll/redraw, or using tokens rather than dice with both sides revealing their "bids" at the same time. All of these reduce the amount of actual randomness by granting the player some level of control. All of them also make a significant part of the gameplay about figuring out the best tactics. If you are careful, you can craft your offset rules to guide the players into a particular mindset.
For example, in one of my Bastard Jedi games, I used the aforementioned card-based system, including all the trading and pattern matching. One thing I did on top of that was give out cards that had red backs as well as the normal, blue-backed cards. These were "rewards" for doing dark-side things, or were channeled from the local dark side miasma. Choosing when and how to use dark side cards was one of the three or four methods I used to make the dark side both more attractive and less clear-cut.
Another big deal if you're trying to make a game feel a certain way is to create stat arcs. This is a system whereby a stat will trend in a particular direction for a particular reason. One example of this is the insanity mechanic in most cthulu games. Another example is any game where you actively spend stats to do things, and can only rarely regain them. Other examples might include dwindling batteries, fame (as a useful stat), and equipment that degrades with use.
It's possible to do positive stat arcs, too, although somewhat more difficult.
Stat arcs are only valuable if the player is given the option of either proceeding along the arc or doing something else. Dwindling batteries dwindle a lot faster when you fire your laser cannons, so it's up to the player: fire the laser cannons, or find another way out of the situation. Obviously, if one choice or the other is clearly the better choice, it's not really a choice at all. If you can either fire your laser cannons or just wish them to death with your brain, you'll never even hesitate.
Somewhat related to stat arcs and sometimes embedded in them is the idea of tradeoffs. This is rare in most modern games, because they have a continuous "upwards and onwards" feeling. However, tradeoffs can really make a game interesting.
For example, I ran a game where you could be radically enhanced, but each enhancement saddled you with more insanity. This led to an interesting situation where players had to weigh how insane they could afford to be (really insane, not the easy insanity most games feature). Obviously, the radical enhancements weren't the only source of gameplay power, or there would have been little in the way of choice. Instead, both equipment and skills played a roll. Just... less efficiently.
There are lots of examples of this in every non-game arena. Sacrifice to get your job done. Even comics have "with great power de blah blah". The closest a game comes is making it so that if you choose the good path instead of the evil path you don't receive the extraneous, useless power-ups for at least another ten minutes.
Cut and Choose
I like this method because it's not very nice. I find that most of the best methods are not very nice.
Using a cut-and-choose mechanic relies on some kind of bidding system where a player will say "either this or this". For example, "I stab him with the sword and he dies OR he stabs me with the sword and I'm badly wounded."
Obviously, whoever is doing the choosing (it's always someone else) will choose whichever appeals to them most. It's not really much of a choice unless they like the other guy, too. But it can be designed with a better set of choices.
The best way I've found to do this is to do a reflect. That is, once the player gives the basic options, the GM (or other adversary) attaches price tags of some kind to each choice. Whichever one the player picks, he pays for, and whichever one is left over, the adversary pays for.
So the adversary might say, "killing the enemy will cost you five karma, but getting maimed is free". Now, if the player chooses to kill the enemy, the adversary is up five karma (or, perhaps, the karma vanishes). If the player chooses to get injured, then the adversary is the one who pays.
The cut-and-choose method does require an adversarial relationship, as it's extremely easy to work together to derail the system otherwise. This is usually best done by making it a zero sum game of some manner. That way, even if they collude, the colluder will quickly run out of resources.
Anyhow, all of these methods can be used as primary or secondary resolution mechanics that dramatically change the flavor of the game. Have you ever used them? Can you think of any others?
There are a lot of specifically interplayer mechanics I want to talk about, but that'll have to wait.