Since the map just has two states - land or water - I wonder if there's a way to represent the same information more efficiently bits rather than bytes.

Any decent compressor will take care of this - and much more.

Here's a map in one bit, where 0 is water and 1 is land: 0