So, playing the high seas map multiple times (during the tournament) made me realize that we really don't have many options when it comes to water units.  It is a chocolate or vanilla situation at the moment... kraken or serpent.  A few more unit types would really help to make watery maps more interesting.
Here are a few of my ideas:
Lvl 1 unit - Deep One/Triton
  This guy is your basic fishman.  10 strength (+10 in water), 16 movement, can't carry heroes.
Lvl 4 unit - Dragon Turtle
  Huge, fire breathing turtle.  4 wounds, movement 8-10 (but can walk on land), very strong, heavy warding.
Lvl 3 unit - Storm Elemental
  Tornado with lightning bolt eyes.  flyer, stack anti-flyer bonus, moves 1 in water, big movement bonus (in water).  This guy can help speed up your boats (fair winds) and help you dominate the skies.  Might have to re-name the current elemental "Magma Elemental" or some such thing.