I just watched some videos and never played the game, but I am interested in SK. That is why I will add some of my general thoughts to the discussion.
My biggest driving force behind replayability (beside a good multiplayer and mod-support in non-singleplayer-only games) is the amount of different races and magic schools I have to test out and play with. Unique endgame units are going in the right direction, but that can only be the tip of the iceberg.
You should focus on the uniqueness of races and magic schools. A good example for different races is in my opinion Heroes of Might and Magic 3, Starcraft, Birth of the Federation and to some extend Disciples 2. My favorite is HoMM3. Playing with the undead, demons or other races lead to unique units, playstyles, buildings, hero skills etc. Add random hero upgrades to chose from, powerful artifacts and of cause different magic schools with beginner to master level spells, and you can play the same map over and over again and you always get another game experience.
Many games did different races and magic schools, but most of them ended up just using the same unit or spell for all races. The developers gave them different names, looks and effect colors, but in the end, it was the same thing and that is getting boring very fast. The best part about HoMM3 is that it created charming and truely unique races on top of a diversified upgrade and magic system. Combine that with city upgrading and a lot of random stuff to explore on a map and I think you have the ideal solution for replayability.
I think many developers go with the "everything the same in different skins - then we don't have to balance it" approach. But that is making a game bland and boring. And as HoMM3 proofs, unique races can be balanced. And SK is not Starcraft. As you mentioned in one of the Let's Plays, SK is a single player game where you fight a mighty Sorcerer. Adding some "overpowered" goodies to SK can't harm. I think that this is a great way of thinking. Go all out, do some crazy stuff and let the player choose from a lot of options like in HoMM3 and you will get not even a great but an awesome game!
At last, I want to speak about an example of how you make a game boring. Many will hate me for that, but I think that Age of Wonders 3 is a boring game. It is a great game and I love it, but it suffers on the described problem above. You have different races and magic, but they all are the same with minor changes. Orc spearman are strong and goblin spearman are a bit weaker, but at the end of the day, every race has a spearman unit or a low level spell that does 10 damage...that is not what I call variety.
P.S.: Adding more huts to the map if a city grows is nice. But is there a city screen where I can see my built structures and the evolving inner city like in HoMM3? A growing city is good, but a city screen that adds more and more buildings with some moving parts (a well, flying dragons in the back etc.) is what I call immersion. That is important to build up a connection to a race or city and it has a collectors's album effect - you want to keep building.
Maybe I should add some smilies to keep the reader awake
->