To create a completely new map you will need one better two 3D artists, 2 texturers, a scripter, someone familiar with the map editor and someone with experience for effects.
If you settle for a map based on an existing map and reuse the background and a bunch of textures, it will be a lot easier. This could be done in a realistic timeframe with 3 or 4 dedicated modders.
Thanks Col.Jessep, That was helpful.
So, around 50k$ for the first map and somewhat less for subsequent maps.
Assuming the 100k per demigod is right, and taking into account Fhoeng's list, we get around 2M$ dev budget. Very rough estimate of course.