On thin ice: Surface order and disorder during pre-melting