So, I've been playing for a while now, and fairly recently beat my second overlord. But I haven't played much since, because I've just been feeling a sense of malaise. It seems like the next phase would really be a wash-rinse-repeat sort of thing; once the overlord falls, it's pretty similar to being level 1 again (well, maybe level 20...). I think what this game really needs are some long-term goals to really keep the player moving forward. Something that can interleave with the overlord cycle.
I don't have many thoughts about this just yet, but the first thing that came to mind would be to really add to the sense of purifying the world. Once I knock these guys down, nothing really changes. The monsters spawn same as before, the tiles are the same, etc. It just doesn't feel like I'm really having an effect.
Putting it simply, I can knock over two overlords way faster than I can win AI war. And it feels a lot less satisfying to do so; there just isn't as much of a gradual ascent to a climactic peak.