It doesn't take terribly long to unlock the whole map, most of the missions that aren't directly related to the main quest you can skip and still unlock the map, it probably only took me around 8 hours of just playing the missions to unlock the whole thing.