Is there an analogue to the role of vapor in liquids and gases, but for solids and liquids? It seems common for an ordered phase to have some amount of disorder present. For example, the average moment of a ferromagnet is less than maximum except at T=0 due to the presence of fluctuations. Also, a liquid is typically only in equilibrium if a portion of it is vapor at the right vapor pressure. Is there an analogue for the solid-liquid transition? In other words, for, say, an elemental solid below the melting point, should we expect a portion of its surface to be liquid at any given time, with this portion increasing steadily until the melting point when the whole thing becomes liquid?
 A: The term you are looking for is premelting or "surface melting." It is an observed phenomenon (which could explain how ice skating works) with some thermodynamic descriptions. 
Basically what happens is the system is separated into two distinct phases, a solid (ice) and a vapor (air). There is a surface energy associated with this interface. If it happens that the surface energy of ice to air, $\gamma_{i-a}$, is more than the added surface energy of ice to liquid, $\gamma_{i-l}$, and liquid to air, $\gamma_{l-a}$:
$$
\gamma_{i-a}>\gamma_{i-l}+\gamma_{l-a}
$$
then it is thermodynamically "cheaper" for the ice to melt on the surface, creating the separation layer. This layer is technically a quasi-liquid with the difference between the quasi-liquid and liquid primarily due to crystalline ordering (i.e., the quasi-liquid still retains some structure).
A: 
In other words, for, say, an elemental solid, should we expect a
  portion of its surface to be liquid at any given time, with this
  portion increasing steadily until the melting point when the whole
  thing becomes liquid?

It is possible for many compounds be part solid and part liquid under the right conditions. As ice melts, you have this condition. If the temperature is set to the freezing point, the ice stops melting and the water remains as is. It requires heat to melt ice and the removal of heat to freeze water. In order for ice to melt, it needs to be at the freezing temperature and more heat is added. In order for water to freeze, it needs to be at the freezing temperature and heat is removed.

It seems common for an ordered phase to have some amount of disorder present. 

An ordered phase for a solid is a crystal. Many crystals have imperfections (disorder).
