you can't go much lower than 150 dpi.. 120 perhaps.. but 72-100 is for screen quality and that will be pixelated when you print. (but viewable).
If its possible for you - don't know the complexity of your map - maybe you could make the map in illustrator, this will produce a vector file which could be much more compressable than bitmap files.

A map of 36x24 inches in 150 dpi should take up about 60 mb space ... if you save it as jpg at quality 8 of 12 it should only take up about 2 megs ... so I'm guessing something is wrong somewhere... if you need help - send me a mail jesper (a) catapult.dk