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.