Probably one of these:
http://www.maps4heroes.com/heroes3/maps.php?keywords=Ukraine&type=&size=&difficulty=&sort=2
http://heroesportal.net/maps.php?user=15745

No, the map is complete, without a Dungeon, the red territory at the beginning has only one city – Kyiv, and there are others (Ramparts). The territory of Ukraine is all green. There are few mines and forests. There are garrisons on the borders with other states, but they are empty. Crimea is protected by a strong garrison; the castle itself is isolated; you can get there either through a portal or through a garrison, I don't remember. There is also a cartographer there. I played it a long time ago on an old laptop in The Shadow of Death, and it was there, besides it, there were XL maps like Return to Avenge, Serpent's Treasure, and Journey to Hell (about 10 maps). Back then, no third-party maps were installed; most likely, they were built into the game itself. But it's hard to find that old build where only The Shadow of Death was included.