What's the fantasy that you're fulfilling for the player? The name should convey this to the player. Banished and They Are Billions are good examples.

Spade and Spear has nice alliteration. Does it convey the time period you're aiming for?

Rook and Pawn is good, too. It suggests chess-like strategy. Is that what you're going for? What geographical markets are you targeting?

Of Stone and Iron sounds more primitive to me, like an early iron age civ game. Is that what you're going for? Do you really need the "Of" in front?

Township is short and fairly memorable for a game name, although others may disagree.

Lords of XXX is generic. It could be good if XXX is really spot-on, though. But in that case you might as well just use XXX by itself.

What are existing products with similar names?

Competitors? You don't want to name your game Township if there's already a game named Better Township.

For which ones can you get a good domain name, if that's important to you?

You might want to grab that domain then while you can. It does make me think of a pre-medieval setting, though.

Banished and They Are Billions are good names not only because they convey a mood (Banished - outcasts surviving against the odds; They Are Billions - standing against an unceasing tide of zombies) but also because they incorporate verb forms, which imply action or intent. Spade and Spear, while alliterative, is only two nouns. Just a thought.

I would actually say that Lord (or other title) of *TownName* is a better than just TownName: it tells player that he will be in the role of ruler and gives insight into the nature of the game -- strategy. This allows to classify game by its very title, the title speaks for itself.

And developing the thought about verbs in the title, you can come along C&C lines and use something like

Build & Defend

Build & Harvest

just search for better synonyms.