Mephe: One of the expansions added the random map generator, which is my favorite part of the game.
IMHO RMG works really poor, I prefer to look for maps on the internet.
However, apart from what said above, there are also small changes in units. 3DO discovered that castle Castle (sic!) is a bit too strong and it changed Angels and Archangels cost - the former used to cost 3000 gold, now they need an additional gem, the latter used to cost 5000 gold, now they need additional 3 gems. It makes a huge difference!
There are also minor things like being able to buy non-upgraded units even after creating a building for upgraded ones, being able to re-visit a place by hitting space, getting damaged by staying in a moat during the siege, being able to leave guards in mines etc.
And mods like Heroes 3 HD (it's really nice to play in 1440x900 instead of default 800x600!) work only with Shadow of Death or Heroes III Gold/Complete (the latter available here) so even this is worth buying.
BTW, this is the first time I buy this game... I've had a standalone SoD and the Gold version before but the latter one lacks some SoD improvements like changing Angels/Archangels cost so I figured I should re-buy it anyway... Unfortunately Ubisoft have kept selling the Gold version instead of the Complete one recently...