Is 他们想拿一张城市的地图。 ok also?
城市地图 is better. 的 is usually used when noun B belongs to noun A: A的B. But when A describes some quality AB without 的 is enough.
I said 一个 instead of 一张
technically it should be 一张 because things like flat things (piece of paper, table) take this counter/classifier 张