Hmm! Well, I think its safe to say that everyone who wants to make games has dozens of ideas right off the bat. Its getting however hard to form these ideas into something that they CAN actually pull off, even harder if its something that they can pull off in GG.
Now you mentioned that you feel a lot of genres are over done. I don't necessarily feel that way, I mean, ww2 and modern conflicts certainly have a lot of titles under their belt but there are still very few WW1 or vietnam themed games. Like there are still thousands of things left undone in those sub-genres.
Now, if you want to make something set in the late or mid 19th century, you have a lot of room to play with.
A pseudo medieval setting like thief, that also has machinery and magic woven into it gives it tons of options and just because it is set in a similar world as thief, does not mean that it HAS to be a thief game. It can really just be a shooter because creating a GOOD stealth game in GG is next to impossible right now. We still struggle with reliable offensive AI so having AI that can differentiate between various levels of awareness and can coordinate? Forget it!
So I'd say sit down for half an hour, pick a time period and design a quasi historic world where you can have a decent shooter with "traditional" FPS gameplay.
Lets look at thief: The setting is somewhat set to steam punk so you can have some melee weapons and some abstractions of muskets, early cartridge types rifles and revolvers and maybe even something tesla themed. For an arsenal alone, you'd have tons of possibilities, maybe even weave the advent of new technologies into the plot of your game.
For example, I had a project once that I shelved pretty quickly because it was just too much work for me.
Skrye, the Heart of Shadows. It was set in an alternate universe where an event similar to WW1 caused enough suffering to allow beings of pure evil to slowly manifest and manipulate our world, you'd be a member of a small order that was fighting not only against that but also against the deeply divided hives of people still remaining. The core plot line is not necessarily the most creative, but it does allow for a whole lot of creative art direction, gameplay and world building down the line.
Just pick a time period, google it, get educated about it and start abstracting the political, social and technological zeitgeist of that era into something that is your own.
-Wolf