On Natural Earth they offer maps at various resolutions. What does 1:10,000,000 mean? Does it translate to the number of points per square meter or mile?
It is the number of meters on the world to the number of meters on the paper. Or any other unit you pick provided that is the same unit on both sides. The wikipedia page explains it pretty well.
So in your 1:10M example it means that 1 cm on the page is 100 km in the real world (if I've done the maths right in my head :-) For a computer data set like Natural Earth the scale is more of a hint about how much detail you can expect.
Could your question be reformulated to: Features of which (real world) size are correctly represented in this data set if its resolution is 1:10m? I had that question to the Natural Earth data set.
After talking to colleagues and finally reading this post Appropriate pixel size when converting vector to raster I made up my answer. I am not sure, if it is right. Probably it is wrong because the number I get (see below) is far to large. So, please correct me.
I think the scale refers to the resolution of the material from which the data set was created (satellite pictures (?), existing maps, ... of 1:10m resolution). There are several data sources from which Natural Earth data set was created. The most coarse resolution of all used data sources as 1:10m. As written in the release notes (http://www.naturalearthdata.com/blog/miscellaneous/natural-earth-v2-0-0-release-notes/) coastlines have a finer resolution than 1:10m
We could calculate the accuracy of our data set by this approach: