It all depends on the style you're looking for. I don't know what you mean about "random". A lot of the elements create aspects of randomness in these tutorials, but it's in a controlled environment. If you don't like something, you can always take a step or two back and do what you need to get it right.
If you want to use picture brushes to get your mountains and hills rather than use bump maps to get topography, then look in the Resources(?) section below Tutorials and How-To and look through brush sets.
When I do my mountains, I make a selection, feather it very slightly, and then fill it with Shaped (Angular) gradient and overlay it onto my map. I'm not sure what the Photoshop equivalent of that is, but I'm sure someone can help you out there.