I just had this same error, even though I installed and ran the game as Administrator. Creating the "random_map" folder fixed it, so I'd second that suggestion, if you're still having issues.
could you please specify in which folder exactly you`ve created the 'random_map' folder?
Thanks in advance
Creating folder "random_map" in the main HOMM3 folder (C:/ GOG Games) works.