I recently created a prototype board game for a game idea I've been working on. If you are at all interested in this sort of thing, I highly recommend this video about user interface design at Apple:
How to Build an iPhone App that Doesn't Suck
That video changed the whole world for me - because it got me started making a paper model board game that I could play with family and see their reactions, without writing any lines of code. It's also a lot of fun to cut out paper tiles and apply artwork.
But the real work that precedes the paper model, is the set of rules that makes the game. I used a spreadsheet for writing out my rules, and could easily generate random board layouts - all of this builds up momentum and generates ideas.
The whole process eventually lead me to some generalizations about both board games and card games (possibly other genres too). If you look at a well-designed game, you might imagine they used this process:
1) Create Layers
The simplest game I can imagine is to flip a coin: heads I get <something>, tails I don't. I'll call this "directly dependent attainment". The attainment of <something> is directly dependent on the coin toss.
Creating layers means adding indirect dependencies for attainment. [And by naming the indirect dependencies creatively, a story-line is generated.] So if we replace "flip a coin" with "open a goody hut", the goody hut may have a 50% chance of containing people (versus being empty). Will the people be friendly or hostile? It depends on <player stats OR technologies researched OR religion OR the phase of the moon>.
So the simple (and boring) coin toss game becomes interesting as layers of attainment are added - and a story is generated along the way. I can think of resource combining, exploration, and technologies as these sorts of layers that make a game interesting.
2) Organize Dependencies To Maintain Parallelism
This is really all about story-telling. Don't believe me? Listen to that guy talking about his last poker game - or my mom talking my brother's ear off about the Scrabble game she won by 1 point (I almost had her!). Maintaining parallelism of dependencies makes the story that much more compelling.
If you add several layers of dependencies for the player to create a specific unit (or issue a specific attack, or build a specific building, etc), each layer should contain related elements. One layer might contain resources (the landscape), another layer contain technologies (the technology tree). Don't put 1000 lbs of iron in the technology tree - it makes no sense!
3) Organize the Learning Curve
This might be more about presentation than it is game-play. If the game is deep, can the game elements be organized such that players don't have to know all the rules before they can start? In this way the game rules themselves are evolving as the game unfolds.
4) Subtlety Creates Depth
Here is where I bang my head against the wall - how are Chess and Go such wonderfully deep games with such simple and few rules? If you watch or play many chess games, you start to see piece development and piece cooperation as key. The story becomes more subtle even as it becomes more simple, less contrived.
These are what might be considered the highest art of gaming - a subtle story playing out, which like a good joke, maybe only a few will understand.
You'll find more discussion about game design in an earlier post Patterns and Rules.
