Measuring distance in a conductive liquid
(Initial, preliminary answer, here.)
There are several possible reasons for your unstable results:

Possibility 1:  Wrong electrodes

Ag|AgCl pellets seem like an odd choice of electrodes for this application.  What are the reasons for using them as electrodes?  What is their surface area?  Their complex shape means the electrical current maybe isn't uniform between the two electrodes.  Also, the fact that you're drawing current through an electrode with an AgCl coating may mean the coating is building-up/breaking-down (which could mess up your measurements) ...  In your current application, it seems like you'd want to use two, big, parallel stainless steel plates (with a lot of corrosion protection!) as your electrodes.  

Possibility 2:  Changing salinity

Depending on the local conditions, the conductivity of the seawater may be changing.  For example, if you are by a river delta, the tides may be washing fresh water between your plates.  Or, if the electrodes are at the water surface in really sunny location, day-time evaporation may increase salinity ...  If either of those are the case, install a second set of plates with a known, fixed electrode spacing to measure salinity, and use that to modify the results from the original set of electrodes.

Possibility 3:  Convection Currents

Is the seawater between the two plates moving?  If so, how fast?  Does the speed change over time?  All of these factors could contribute to unstable electrochemical readings, too ... If so, you may add mesh or baffles to create more-consistent flow conditions. 



(Follow-up answer, here)

As far as I can tell, you're method sounds alright from an electrochemical perspective.  Cathodic protection is fine for minimizing corrosion.  Having "known distance sensors" will avoid problems with changing salinity, etc (as you mentioned).