I think, for start, it should be possible to make harbor "outside city walls". I mean not connected to rest of the city, similar to resource buildings outside town . That way it may easier to both make cities at optimal positions, without compromising very rare beach tiles, or being forced to build cities up to the beach, just to be able to get harbor.
Here is how I was forced to build one town, just to be able to get to the tiles that can support harbor.

Note that in picture, harbor is still in construction.