Is non-randomly-sampled historical data representative?
Samples don't need to be random to be valid, it helps but it is not essential especially if exhaustive, consistent, and has a large sample size, especially when dealing with observational studies. Representative sample is different than random sample. Remember we are not trying to attain the global temperature to the highest degree of accuracy in one instant, we are trying to measure the change in temperature over a long span of time. Thus consistency in location is more important than randomizing location.

The fact that the sampling points do not move is essential, we know temperature is affected by regional conditions if the samples were re-randomized(moved) with every measurement it would make it less accurate not more. Remember what is being measured, the change, because the sampling points are not moved the the change will be accurate because it essentially becomes a stratified sample. If I am measuring changes in engine temperature for instance I don not want to measure at a different point each time, as long as the points(locations) are consistent the sample will retain high accuracy. A random sampling would be LESS accurate because it would invite confounding because we know the distribution of temperature across the engine (or globe) is not random. Any shift in location between measurements would invite confounding data. Almost no science uses a truly random samples, it's just not possible. Consider things like exhaustive sampling, cluster sampling, stratified sampling, and systematic sampling all are used more often than true random sampling and each is more accurate than random in the right circumstances. 

Consider an example, say you are trying to measure the temperature change in an engine over time. Where on the engine I attach my sensors does not matter as long as I do not move them, especially if I put many sensors on it. I could put thirty sensors all on the left side engine, and it would measure the change in temperature very accurately, compared to moving the sensors between every measurement. Don't fall for the perfect solution fallacy. Also remember this is an observational/descriptive study by its very nature.  

Each point on the map is more like a repetition, the real independent is the time at which they are sampled, which is either stratified or clustered depending on which study you refer too. Note that multiple sets of data points are also compared. NOAA, BEST, etc. are each independent data sets that can be compared, and show the same pattern.

High and low are used for measurements because that is all that was recorded in the oldest measurements, so changing the format would require throwing out all that data, drastically shortening the sample size (loosing more than half the time span). In this case the accuracy gained by the much larger number of samples is more than would be gained by a random or grid location. Random is rarely possible with historic data which is why the size and consistency of the data set is so important. The nice thing is these are also compared to other sampling methods on other time scales to test to see if they show the same pattern. Historic scientists are aware of the limitations of their data which is why independent verification is so important. 

Now consider ice core data, I was surprised when you said surface temperature was the most used, I see ice core data far more often, because it records a much longer span of time, and records other things (like $CO_{2}$ content) as well. Again each core is a repetition and the core can be sampled in a random or stratified way, stratified is the most common because it is more exhaustive in a core sample. Ice cores are also compared to ice cores for m other locations. 

Another consideration is cross-comparison, that is the use of multiple independent forms of measure, ice core compared to satellite, compared to surface, etc. Dozens of different forms of measurements/experiments are compared and show the same pattern. 

This is probably one of the best overviews of the science I have seen. It is a little old (2013) so if anyone has seen a more recent version I would love to use it instead.