I agree that once you've figured out how to get off the ground and not expand too hastily, the game becomes very easy. Once you're over the hump, the biggest challenge is traffic, traffic, traffic, and then making sure you have enough services and facilities to cover everyone.
I would love a disaster mechanic to throw a wrench in your plans (I accidentally flooded my city by building a dam too high, imagine having to deal with that for a a week), as well as external factors such as booms and busts in particular industries, and more involvement with your neighbours.
Something like the quests in Civilization: Beyond Earth could be fun too. The game will give you a challenge, and then you have to decide what to do with the reward, and make decisions with clear tradeoffs (although this got repetitive in Civ:BE).
It would be interesting I think to pay a heavy toll for demolishing buildings that are already standing so you really have to think about evicting people.
Great idea. At the moment there's no real punishment for doing so. Would be cool to see crime rates and homelessness go up, resulting in more riots, fires, and decreased land value.