Sumer 3000BC (-ish)
I couldn't find a good detailed map of Sumer for this time period, so I made my own. Some of these cities might be temporally dislocated by a paltry 500 or 1000 years, but at least the physical distances are pretty much dead on. Ask your local sumerologist to be sure. If you have a better map, please point me to it. Seriously.
This isn't a map I would take on a time traveling mission, but it's probably good enough for a game about aliens nuking elves from orbit.
The Persian Gulf reached far further North in 3000 BC than it does today, as seen on my map here. Today it's shore would be found south of this map's edge. The forests and swamps are all my own fiction; but the hills, mountains, and rivers are pretty accurate for the time period (I believe). The landscape changes a bit every spring when the Tigris floods it's banks and spills water into it's surrounding hexes. Notably a huge area south of Der becomes a vast swamp, and the hexes east of Sippar become swampy as water pours into the Euphrates. This can cause some flooding along the Euphrates as well, turning some hexes downstream into marshland. By summer the flooding is mostly resolved, but I reserve the right to put swampy hexes wherever I see fit.
The Cities and their Patron Deity
Kesh - Ninhursag (The Great Mother, Fertility, Birth~wife of Enki)
Nippur - Enlil (Lord of the Air, Storms~Enforcer/Heir of Anu)
Isin - Ninisinna (Lady of Healing, Herbs, and the care of animals)
Shuruppak - Ninlil (Lady of the Air, the gentle spirit~wife of Enlil)
Uruk - Inanna (Goddess of Sex, Love, and War~sister of Ereshkigal)
Larsa - Utu & Sharida (God of the Sun, Judgement, Watcher of Oaths & Goddess of the Dawn)
Ur - Nanna (God of the Moon, Diviner of Fates~father of Utu)
Eridu - Enki (Trickster God of Water and Magic~brother of Enlil)
Bad-Tibura - once Dumuzi (hedonist God of the Harvest) now Lulal (~son of Dumuzi and Inanna)
Zabalam - Ninshubur (Queen of the East~minister/lover of Inanna)
Umma - Sharra (Singer, manicurist, hairdresser, warrior~son of Inanna)
Girsu - Ninurta (Goddess of Bravery and Battle, Lordstress of the Amazons)
Lagash - Nanshe (Goddess of Prophecy, Fishing, and Social Equality~daughter of Enki)
Urum - ?No Patron Deity?
Kutha - Nergal (God of Wasting Death, Disease, Starvation, Exhaustion)
Niru - ?No Patron Deity?
Kish - ?No Patron Deity?
The Far North
Sippar - Utu & Sharida (Sun God & Goddess of the Dawn, Flagellation, Punishment, and Penance)
Tubtub - Imdugud (The Breathing Beast, the Thief of Fate)
Eshnunna - Ninazu (The Benevolent Healer of the Underworld, Thrall of Ereshkigal)
Der - Ningishzidda (The Lizard King~son of Ninazu)
The Far East
Suza - Insheshinak (The Undying God, The Waker, The Sleepless Need)
Chogha Mish - Kirirsha (Lady of the Golden Dawn, Squirmer of the Wrym)
Distant Lands (off the map)
Martu (In the Northwest, ancient Syria)
Gutium (Land of the brutal Wildlings of the Zagros Mountians)
Dilmun (The Floating Island, sails to Meluhha and back again each year)
Meluhha (Indus valley region of ancient India)
Magan (Somewhere to the South and West, reached by sailing around the Arabian Peninsula)
I scaled the map to a Sumerian unit of measurement. Each hex = 1 da-na = 2 hours. Sumerians divided the day into 12 da-na, and measured long distances by how many da-na it took to walk somewhere. I think that's neat and all, but using da-na during the game is probably more trouble than it's worth; so....
6-ish mile hexes. It takes about 2 hours to walk across a hex while carrying standard gear and supplies.
On easy terrain: grasslands and roads
Walk: 4 hex/day = regularly stopping to rest, the party is battle ready and in good spirits
March: 5 hex/day = NPC morale check and weariness penalty at last two hexes
Run: 6 hex/day = NPC morale check and weariness penalty at last three hexes
Run like the Wind: 8 hex/day = Totally unencumbered, weariness penalty every hex after the first
Weariness Penalty (cumulative but temporary): -1 Con, and -1 to most die rolls (not saves)
Every 4 hours of rest will remove 1 from the cumulative weariness penalty.
Rough terrain reduces your speed, and running for hours isn't really viable there (except on trails).
Walk 3 hex/day or March 4 hex/day: Shrubland, Forests, and Hills
Walk 1 hex/day or March 2 hexes/day: Marshes, Heavy Forests, and Mountains
Coracle (Quffu) - a man-sized leather bowl with a wooden frame. Typically paddled down the river, then carried back home on the road using shoulder straps.
Reed Boat (Kalakku) - Lots of shapes and sizes, from a reed canoe up to something resembling a viking longship complete with sail and weird animal head prow
Wooden Boats - You'll see the occasional wooden raft or dugout canoe, but they aren't common. The Euphrates and Tigris have swift currents, especially in the spring. Reed boats are cheaper, lighter, and much easier to bring upriver.
Rowing: 5 hex/day downriver, 3 hex/day open water, 1 hex/day upriver or through marsh
Rafts: subtract 1 hex/day
Reed boats using 6 oars and a sail add 1 hex/day