For songs of the sea, I've always liked "The Diamond" and "Fareweel Tae Tarwathie" Two great songs with sad stories behind them.

For sea shanties, give me anything that gets the audience stamping feet and joining in. "Rio Grande" or "South Australia" seems to work well, or "The Alabama", if the wind's in the right direction.