Thanks everyone!

The consensus seems to be a Northern Fulmar. It makes sense. It's
funny how far off I was even though I had several Fulmars on the trip.
I kept looking at the photo and every tubernose and alcidae in Sibley's
and just couldn't see the match.

A few things that make the ID interesting:
(1) The wings seem very short, but that's just due to the angle
(2) It is a pretty dreadful photo. The resolution is low, and the color
/ white balance is horrid
(3) The bird is looking pretty ratty from molt.

For comparison, here is a pretty clean photo vs the mystery.

http://w1.decorte.us/pix/Northern-Fulmar

http://w1.decorte.us/pix/album41

As for the gull, the census is Thayer's. I was leaning towards Thayer's
but using Sibley's for reference, there seemed to be too much black in
the wing tip.

Maybe I could get a more pelagic experience by joining the cruise ship
crew? :-)

Thanks again,