What is the difference between _Procedural Generation_ and _Random Generation_?

Question

Today, I got into an argument about the term "procedural generation".

My point was that its different from "classic" random generation in that procedural generation is based on a more mathematical, fractal-based, algorithm leading to a more "realistic" distribution and the usual randomness of most languages are based on a pseudo-random-number generator, leading to an "unrealistic", in a way, ugly, distribution. This discussion was made with a heightmap in mind.

The discussion left me somehow unconvinced about my own arguments though, so, is there more to it? Or am I the one who is, in fact, simply wrong?