Generating contour lines from a 3D terrain is very easy. Generating 3D terrain from contours is possible but more difficult. If your wanting to shade the terrain then you will need it in 3D if it is to be done by an automated process. If you have a height map that is lower resolution than you require its not so much pixellated but more of a smooth and blobby appearance. What you lack in low res height maps is sharp transitions like cliffs or details. So its bad news for fjords and alike. One huge problem with height maps is that they cannot represent undercuts and have a hard time with vertical cliffs. On the other hand neither can contours as they all pile up into one single line.

If your fictional world has earth like appearance and geomorphology then you can get hold of some raster height maps in greyscale or LIDAR from a variety of places like NASA etc and just stitch patches of them together to get a somewhat realistic height map version of the ground. Then you can obtain your contours from that.

Generating good heightmaps for a realistic fictional world is always a hard task.