Whether it's best to start designing a game with either theme or mechanics is hotly discussed topic (spoiler: different games/designers do it differently).
But whichever way you start, I believe it's best to iterate using both approaches, blending crunchy mechanics and silky theme, like a perfect baguette.
To do this, imagine you have a see-saw, where each side represents the influence of either the mechanics or theme.
Perhaps you start mechanics-first. You iterate on that awhile and develop a promising, fresh mechanic that seems to have legs. During this time, imagine you're adding weight to the mechanics side of the seesaw:
At some point, you reach diminishing returns from mechanical exploration - that side is really weighed down. You've made some real progress, but real problems are starting to show. The game just hasn't come alive yet, or there's no excitement. So now you can start viewing your game through a theme-first lens.
Now try changes that support the theme, first and foremost. It's not that you're ignoring your robust mechanics, but at the moment, you're more concerned with bringing the theme of your game to life. As you work and find changes that resonate, you can imagine the theme side of the seesaw getting heavier, lifting the mechanic side and making them more important again. When the thematic improvements to your game start getting difficult, it might be time to switch back to a mechanics-first lens. In this way you go back and forth, alternately looking at your game from one lens or the other, looking for changes that help the side you're currently most concerned with.
I've found that this approach can lead to real breakthroughs, especially when I'm really stuck. A mechanical problem can often best be solved through a thematic solution! And when I no longer know where to take the theme of a game, I can often look at the mechanics and find the answer, somehow staring at me through the spreadsheet. I've noticed these aren't just decent solutions, but truly inspired ones.
If you decide to try this, here are some questions that might move you forward:
What parts of the theme are feeling absent? What crazy changes could bring it to life (suspend disbelief temporarily)?
What mechanics are actively getting in the way of the theme? Are there assumptions (especially due to balance and pacing) that can be questioned?
How should the game feel? If there's a world of the game, how does that feel? Abundant, stingy, limited, tense, free, optimistic, methodical or intellectual? Carefree or full of repercussions? What changes could I make to create or accentuate these feelings? Are there mismatches (for example, a game about planet-hopping, but fuel is expensive)?
Ignoring complexity, implementation difficulty or balance, brainstorm 10 rough ideas. Do any of them excite you? Why? Explore this space.
What are the advantages of the current mechanics? How can they be leveraged more? For example, if random starting state is a big aspect, how can that become more random, with more possibilities? Or if pre-constructed decks are a big part of onboarding, should there be more of them, for different personalities?
How can I change a parameter of an existing system, before adding a new system? Could I remove an existing system in the same way? Ie, if new units are entering the game too fast, instead of adding some kind of "inertia", would simply changing the starting number of units address it enough? Or could the game timer be shortened?
What mechanics are most complex, trickiest to implement or balance, or the most problematic? Why? What are some possible simplifications? Entertain them playfully before discarding them. If something isn't working, is it possible that you can just remove it entirely (it may elicit a gasp if you realize it's true)?
Before adjusting a single mechanic, are there multiple problems that seem like they could be related? What are some ideas that could address all of them? Brainstorm 10 ways that could possibly do this. Do any of these excite you?
In my view, the world's best games have both strong theme and strong mechanics.
They seem built for each other, and may seem to not be able to exist without each other. The more one learns about the mechanics, the more one understands the theme, the world the game lives in, and vice-versa. There doesn't seem to be a way to even move the mechanics out of the game without breaking them. But many designers iterate largely from only one viewpoint.
This is definitely more of an art than a scientific methodology. But when I've felt stuck with either the theme or mechanics, I've often had the biggest breakthroughs when I looked for a solution from the other side.
Read Part #2.