Heroes of might and magic III: Horn of the Abyss
http://heroescommunity.com/viewthread.php3?TID=39830

Core features.
-New fully playable town – Cove.
-New war machine – Cannon. Available at Cove’s Blacksmith
-New artifacts and artifact sets
-New banks and conservatories
-New types of map objects
-New heroes
-Towns change their appearance, depending on Fort level
-Map editor
-Support for bigger map sizes (Huge, XHuge and Giant)
-A lot of balance fixes (like finally nerfing the necromancers or making life easier for Tower and Inferno)
-A lot of RMG fixes (for example, removing all sea elements from non-sea random maps)
-A lot of graphical fixes (like, really a lot… original game had plenty of graphical bugs)

HotA was actually released? When did that happen? It seemed to be a never-ending story with very little visible progress (but I didn't check for a long time).

Thanks, it looks pretty cool

Awesome, wake of the gods was a bit too crazy for me, but this looks great! Definitely going to try it.