Theme first or mechanics first? It doesn't matter.
Game designers often get asked whether they start with theme or mechanics, but I'm never quite sure what the questioner is hoping to glean about the process of game design. It seems to assume a binary, decoupled state of gameplay. It even seems to be the definitive divide in Euro/American game design. (We can address our very weird tendency to ascribe game design to either America and Europe another time, but that's worth discussing too.)
The truth is, if your game is working as it should, no one should be able tell whether you thought of the theme or the mechanics first.
If you focus too much on theme, the mechanics might be burdened with too much simulationist cruft. The game is inaccessible to all but the tiny demographic who really cares about how accurately you represented that theme. In my case, if I begin with a theme, I also spend a long time in development.
If you focus too much on mechanics, they might be too abstract. Your game might have a lot of depth, but that is only worthwhile if players can see that depth. A theme can help create the metaphors and allegories that make the strategy and tactics much more accessible.
So here's my ideal process, call it a sandwich. It's not right for everybody, and it might not even be right for me in a few years, but for now it's been the most efficient method for me to design fast and iterate rapidly.
1. Find an interesting interaction between people.
Haggling for a deal? Coming to an agreement? Divvying up resources? Bluffing? Getting rid of stuff while avoiding getting new stuff, or vice versa? There is usually a mechanical element implied in this interaction, often a slight twist on an existing mechanic from an existing game.
For example, I thought it would be interesting if players were forced to divvy up a supply of resources into different play spaces, those spaces would then score in different ways and reveal a little bit of information to other players about their long-term goals. You've seen this sort of gameplay in several games, including Guildhall and Biblios.
2. Find a theme that fits the interaction.
You often hear gamers complain about games whose theme feels "tacked on." As if the whole game had been designed and developed with no thematic input at all. To avoid this pitfall, I try to bring in the theme very early on into the design process.
For example, in order to score points, you have to reveal some cards and have matching cards hidden in your hand. Thus, players could see what you may be trying to score, but couldn't be absolutely sure. I saw the interaction between players as being sort of "coy." I couldn't resist the pun of "koi pond," so I pursued that theme.
3. Let the theme suggest secondary mechanics.
So at this point you might say I start with mechanics, and to some extent that is true. It would be more accurate to say I start with a mechanic, singular. But I go no further until I've found the right theme to fit that mechanic, then I filter any further development through that theme.
For example, I decided the game would be about koi ponds, in which players collect, display or release koi fish. What other elements of koi ponds might be interesting gameplay interactions? Perhaps a competition for visitors? Best decor? How about fish breeding? How about the pests that can be a nuisance to a koi pond? From all these questions came the secondary mechanics of Koi Pond: You deploy turtles, cranes and housecats in order to score points from your opponent's collections. You release koi to the river in order to win ribbons. Those river koi eventually flow into a central lake accessible to all players.
Okay, sure, you can call me a mechanics-first designer, but I'm also a mechanics-last designer. I'm thinking about theme and mechanics all the time, at the same time. My ideal is that both are so integrated with each other that the game just makes too much sense for the theme and mechanics to ever be decoupled. They're just supposed to be that way.