If I start with Fishing and my capital is on a coast with a seafood resource, I'll usually build a fishing boat before a worker so my city has time to grow to size 2 (and then the seafood will help build the worker). By doing this though, I'm forgoing building a warrior or scout to explore.
I like coastal cities. I like trade routes, and harbours are good for those. Most players don't care much about trade routes though, and as I'm pretty bad at the game, chances are they're right and I'm wrong. The seafood health bonus you get harbours is nice though. Somehow, cities never feel complete to me unless they're on a coast (and hence able to build coastal improvements). However, coastal cities do have lousy production, unless you use Slavery and have lots of food resources there.
In particular, I insist on a coastal start for a OCC. The health and trade route bonuses from the harbour are too good to miss in that siutation, and a non-coastal start would mean no navy, ever! That said, you wouldn't necessarily need one, except perhaps to make contact with civs on another continent.