Without nailing down a very specific play…this is only an example of what I am trying to describe, and that is unifying the different parts of the game into one connected flow to create a unique character/experience.
For example, right now all of the tiles in a given area of the same type feel relatively the same. So I came up with the idea of "liberating" a tile, and once liberated, that tile could be coerced into some mechanic that would either contribute towards the settlement, the overlord they are rebelling against, or permanent player changes.
Right now you have a lot of side views of different kinds of houses and buildings; what if some of these were reserved for a liberated tile? For example, upon liberation, you use the smoke graphic and over the course of a few "turns," buildings appear and NPC's began to mill around and perform some kind of default construction of materials that get sent to your settlement, perhaps donate troops, or even unlock characters (personas?) that you can play. Allowing the player to configure that is a bonus, and even a, "thank you for liberating us from Overlord Foobar's henchmen. As a token of our thanks, we offer you…" Makes Toad look stingy.
What does this accomplish?
1) Real rewards that offer choices, acknowledgment and gratification for completing what amounts to a "level. " The settlement game isn't that in-your-face right now, doesn't really feel like you're getting anywhere when you complete a level.
2) For the settlement, the more tiles liberate, the greater the rebellion. Your choice in how to represent that rebellion, well, I think that's where the cleverness has to come in. That's where you decide what benefits and rewards we can choose from. If the overlords castle was a little bit more tricky, I think that could make some very appropriate rewards. Personally, I would like a mercenary to travel with me and take the fall. Perhaps even more dramatic, maybe have 20 NPC's rushing the gate at the same time. Even if they die, that's fine, it just has cool factor.
3) Your actions actually change the world. Right now, we have the distinction of making the world even more desolate by removing monsters.
I don't really understand settlements yet, as far as where you are going with it, but it should be something that grows with the player with each successive settlement, or perhaps give one main settlement that grows over time.
It would be nice if you gave NPC's a set of five behaviors, then we could have some kind of emergent town behavior. If this was meaningful in what their contributions were to the rebellion, even better. Having random word bubbles above some of the NPC's occasionally could be kind of funny. It adds a little bit of liveliness.
The overlord needs to be scaring the crap out of people, act menacing, and if that's not possible, play the comedic villain. Maybe send notes to the settlements (could do the same thing that the epitaph thread does, except make them letters from the overlord). Perhaps they could be read as speech bubbles by the NPC's.
I want my character to be different than someone else's at level 60. If we are all running around with the same look and the same spells, is just not as fun. A specialization would be nice. Red mage, black mage, white mage... just as an example.
And finally, I think that allowing people to make levels was a great idea. There are relatively harmless modifications you could allow, such as sprites to cover existing character/enemy skeletons. To some extent, modifying the game to allow for future purposes, keep that in your heads right now as you work on it. More hooks, more hooks.