I've spent a good amount of time from boats in the 25 to 46 foot range (sport fishing where finding birds can lead you to your quarry, and on cetacean watching trips) and have also used binoculars from large ferries. My quick thoughts:
7x50 - the classic marine format. Ease of view of the extra-large exit pupil makes them a pleasure to use, and their main disadvantage (size/weight) is less of an issue when you are on board. 7x mag is definitely more stable than 8x let alone 10 (the latter is not a realistic option from a smaller vessel unless stabilized), but is a little underpowered, especially if you're trying to identify individual smaller seabirds at some distance. Trying to pinpoint plumage or other features on a single bird, especially a smaller bird like a storm petrel, is a totally different proposition to trying to spot a big flock of birds over a school of tuna. If you are chumming and bringing them closer to your vessel, obviously it's less of an issue. The point chill6x6 makes about the primary use for this format being navigation is quite sound - other vessels and even marker buoys are much larger than birds, and normally not too much of an issue unless you're close enough to risk hitting them!
Field of view of most 7x50s is quite limited on paper compared to other formats, but in practice I didn't find it was such an issue.
7x42 - I've used my 7x42 Dialyt, P model, at sea and found it similar to the 7x50s. Larger field of view could be an advantage. You'll need to make sure any non-marine binocular used at sea is carefully cleaned as salt water is notoriously corrosive - even fishing reels need to be sprayed off with freshwater.
8.5x42 (Swarovski Fieldpro) - I've used my brother's from a 40-footer and also from a large fast ferry. Definitely more shaky than the 7x models but the flat field helps with ease of use and the extra magnification also helps. Would not use from a smaller vessel. I've tried 8x30 from boats in the 25 to 30 foot range and found them very difficult to use.
IS would be the game changer here. The Fujinon model denco linked to seems to be highly rated by those who spend large sums of money (including participation in tournaments with even larger sums of money at stake) trying to find marlin tails protruding about six inches above the surface. These folks are absolute experts at that game, but the 4 degree field of view seems very limiting to me (I suppose the tournament captain's recommendation would be to hire more spotters!). I'd like to try something like a Canon 10x42 IS as my experience of its IS feature (albeit on land - have not tried that one at sea) is very positive and I think the wider field of view would come in handy.