I personally am attracted to the idea of abstract games, with little or no theme. However, that is difficult to come up with a large number of unique, interesting cards.
Some other ideas from good books: Going Postal is a good book, it's about a thief who is released by the monarch (a very secretive and manipulative person, although ultimately benevolent.) on the condition that he revive the local post office. However, the klock towers (or something like that) are an evil corporation that run as series of the towers that send telegram like messages. It's kind of fantasy, in that there is magic and stuff, but more like an 1800s industrial city, in the transition between magic and technology.
Also another book that was interesting, (don't remember it's name) was an ancient city in the middle of a vast ocean, that was broken and corrupt, basically anarchy, because it suffered chaos-storms. These were like rainstorms, but those trapped in them would be subjected to completely random effects. Some would start growing flowers out of their heads, and some would have their heart teleported 3 inches to the right. The city was also overrun with ghost like creatures that could kill with a single touch, and the mechanical police, that were still alive since the Ancients caused the chaos storms with their machines.
Just an idea, what about a theme that doesn't have to do with fighting. Some other conflict, but not units fighting each other.
I just feel that we should attempt to make this as unique as possible.
In addition to a theme, we should choose a game style. For example, do we want it to be played quickly, long games, focus on mindgames, play with a few cards, or as many as possible, heavy deckbuilding emphasis, etc.