If you're designing theme-first, you must choose a fascinating theme. When you tell people the theme, they should immediately be interested.
Players and publishers are not interested in "a pirate game" or "a train game". To a jaded publisher, a game about the sewage system is vastly more interesting than another game about zombies. I kid you not. Your theme should be interesting, but doesn't need to be totally zany. Zany is definitely good though, if you can manage it. If a publisher somehow gets around to evaluating a boringly-themed game, and the mechanics interest them, they'll just retheme the game to something else — of their choosing.
My game Radlands was originally a generic futuristic game, but the publisher changed that to an over-the-top Mad Max theme. It was a huge improvement.
Don't make your game literally ten times harder to publish, by choosing a boring theme. It's ludicrous to have complete freedom with the theme, because you're designing theme-first, yet not actually choose an interesting or novel theme.
Even if your theme has been done before, and you don't want to change it, you can still put a new twist on it. If you have to do zombies (which you shouldn't), make it "zombies in Japan" or "zombie cats" or something.
You can just choose an amazing theme with no relation to your mechanics.
I would've made the game about animals, or something with more variety, but Wingspan's bird theme has helped make it hugely successful.
I'm not really wanting to just evoke the theme itself. The theme leads to a larger feeling of the theme.
I don't just want a pretty, pirate-themed game. I want to feel like a pirate — roaming the sea, attacking other ships at will.
I don't want a spy-themed game. I want to feel like a spy — planning secret moves, and having secret information.
In case this distinction isn't clear, think about some examples from real life for a moment, without thinking about board games.
Imagine you're a kid arriving at a theme park, and there are more rides and activities than you can imagine.
Imagine the feeling of exploring a haunted house.
Imagine you're at the edge of a vast, unexplored wilderness.
Think of a game you really like. What is the feeling you get when you play it, or that you got when you first played it?
Turning a real-life feeling into an actual game is extraordinarily hard, but you only need a small amount of that feeling to come through in your game, for it to make an amazing board game. This is done not by slapping a theme on your game rules, but by carefully choosing game rules that bring out your theme.
The size of the theme should also match the size of the game. Do not try to attach a big story to a small game.
Azul is a game about arranging coloured tiles. The theme is that you're making a Spanish tiled floor. That's an appropriate theme.
Codenames is a word association game. It's themed as a game about secret agents. That theme is completely irrelevant to the game.
In a friend's prototype, you place object tiles around cat cards. When a cat is surrounded by objects, you add up the points on the tiles, to see who takes the cat. This game was mechanics-first, other than the very general "cat" theme.
We went through all kinds of big-picture themes for the game. It could be a cat adoption place. But why would you adopt multiple cats, by placing objects around them? I suggested a cat cafe. That was better. However, nothing else in the game said "cafe". We agreed in the end that the story was just that you were having fun with cats. You give them objects, and they like you, and come to you. That was the extent of the story. It was the correct choice, because it matches what the game actually is.
I've seen numerous basic number or colour-matching games, with some kind of epic legend as a theme. Don't just pick the most awesome theme you can think of. Find whatever matches your game best.
Leave your theme broad, so it doesn't restrict you. Don't choose the exact time period, location, and size of your theme at the start. As you develop the game, your choice of individual cards and resources will help narrow things down.
Some themes are inherently single-player (or cooperative.) If you're exploring a land, or going on a journey, for instance, how is this a competitive game? You can do these themes, but you might need to bend the theme, to explain why the players are competing.
I made a game where the players were trying to survive as shipwrecked castaways. That's an amazingly relatable theme, in my opinion.
I didn't want the mechanic of the players helping each other, so I made the castaways criminals. I didn't want player elimination, so I just decided that you would lose points rather, rather than die, if you failed to sustain yourself. But what is victory, in this game? I decided that the player who survived this experience best (by having the most points at the end) was the winner. This was all a bit strange, but none of it impinged on the feeling of being a castaway, which was well-supported by the other game elements.
You need to be able to explain your theme in a few words. Telling a long story you invented, is not a theme. It's just a random collection of things.
I'd like to play a game about running an ant colony, or creating a mosaic. I know what those things are, and I want to play them in a game. I'm not so interested in being the Archmage of Kronglor, or recovering the Five Galactic Shards of Kozmog.
People need to be captivated by the theme of your game, and that's only going to happen if they can actually understand it.
I've designed games on all kinds of different themes, and people's reaction was usually fairly muted. Then, I started making a game about kids roaming around a neighbourhood on their skateboards, and getting up to all the mischief that kids get up to. This theme resonated strongly with people, and they were immediately fascinated and engaged by it. If you're designing theme-first, this is what you should be aiming for.
Having said all this, I don't recommend starting theme-first. It's much easier to use a preexisting mechanical framework, that's known to work in other games.