Below is the result of a hierarchical function expansion on a triangular mesh rather than the square mesh most of these applets use. The triangular mesh has the advantage that the underlying polyhedron can be an icosahedron, which will produce much smaller edge effects than the underlying cube that must be used with a square mesh.
The terrain is shaded based on local surface normals and a light source that rotates around the sky. On browsers with interpreted java, this can be quite slow to start up.
My first thought was to generate finer-level points from their two coarser-level nearest neighbors, but this creates artifacts: the most extreme terrain tends to lie along the coarsest-level grid lines. This is because the points on the interior of a coarse-level triangle never get averaged back in to any of the points on the edge or in the next triangle, so two adjacent coarse-level triangles will develop in complete isolation from each other.
To get around this, I switched to another averaging scheme that also brought in next-nearest neighbors. I tried various weighting schemes, including several different (and mutually exclusive) "correct" schemes that I derived, but the best scheme for eliminating these artifacts seemed to be even weighting of the four points.
Here's an illustration of the averaging scheme used in the applet on this page:
The source code for this applet is available. Comments therein talk more about the choices of averaging schemes.