Here is a wiki page and tool may offer some assistance. It isn't a rule of thumb as it is a complex method, but it may serve as a good stepping stone to a rule of thumb:
Grid size calculator. Nov 5, 2008. In Spatial Analyst wiki. Retrieved
Nov 11, 2015, from http://spatial-analyst.net/wiki/index.php?title=Grid_size_calculator
This page seems to standardize methods for determining the appropriate DEM resolution based on characteristics of a given topography/contour map.
The useful tool I referred to is the GRID_CALC.xls available for download at the top of the page, "A simple step-by-step grid size calculator". In that tool there are various methods to derive a grid size recommendation, and with contour maps as the basis I think method 7, Complexity of Terrain, is ideal. That method's instructions are, "you can either make a transect study and observe every time the topography changes (inflection point) given a vertical precision or if you use contour data, you need to estimate the average spacing between the contours." The tool offers a coarsest, finest, and best grid cell size recommendation based on either of those inputs.
There is also a relevant description on that page, under Selection of cell size for geomorphometric analysis:
In this case study I will demonstrate how a grid resolution can be
selected from a map of contours, i.e. a dataset consisting of lines
digitized from a topo-map. Contour lines were extracted from the 1:50K
topo-map, with the contour interval of 10 m and supplementary 5 m
contours in areas of low relief. The total area is 13.69 km^2 and
elevations range from 80 to 240 m. There were 127.6 km of contour
lines in total, which means that the average spacing between the
contours is 107 m. The grid resolution should be at least 53.5 meters
to present the most of the mapped changes in relief. I then derived
the distance from the contours map using the 5 m grid and displayed
the histogram of the distances to derive the 5% probability distance.
Absolutely shortest distance between the contours is 7 meters, and the
5% probability distance is 12.0 m. Finally, I can conclude that the
legible resolution for this data set is within range 12.0-53.5 m.
Finer resolutions than 12 m are unnecessary for the given complexity
of terrain. Note that selection of the most suitable grid resolution
based on the contour maps is scale dependant. For the contour lines
digitized from the 1:5K topo maps, the average spacing between the
lines is 26.6 m and the 5% probability distance is 1.6 m. This means
that, at 1:5K scale, the recommended resolutions are between 1.6 and
All of this information I'm referring to often cites the following article:
Hengl T., 2006. Finding the right pixel size. Computers and Geosciences,
That paper doesn't add much new to the above except for including equations for computing the coarsest, finest, and best resolution recommendations based on the considerations described above.