As high up as you can get, and as far forward or aft. Liberty Island, and Ellis Island as well, are to starboard. Also, stick around for the "sail-under" of the Verazzano Narrows Bridge. From the top of the ship, you can see the rivets holding it together.
All in all, Manhattan is the best sailaway experience!