I wasn't suggesting gray borders on things, just drawing over the river and coast with a not-quite black pen. What I was trying to describe is similar to a line drawing containing the mechanical graphical elements (lines, text, borders, etc.) drawn on top of a sheet of thick vellum with the original saturated image aligned underneath it.
Another small update. I am now mostly content with the "physical" map, I think it gives right the impression I want for this world. I think that the spaced names works better, I wonder why I did not notice that before (btw, is there in photoshop a way to make that automatically? I had to manually add spaces between the letters, which does not satisfy my innermost OCD core).
I cannot find good colors for the "political" map, any help or suggestion would be greatly appreciated.
I decided to add towns (small triangles) and fortresses, in addition to cities (circles) and large cities (squares), I am ambivalent toward these additions. I also have to make up many other names, always the worst part for me.
It depends on your version of Photoshop I suspect, but in CS6 if you have the Character dialogue open (go to Window along the top menu bar and it should be in the list), there are various elements of a text box that you can modify, including spacing between individual letters. In CS6, the symbol in this dialogue box you'll be looking for is a VA with a two-headed arrow underneath, and it is set to 0 by default. There is a T also with a two-headed arrow, but that stretches or squishes the text.
I have an older version of PS and I know that you can change elements of the text of multiple layers at the same time. Just select them all and make the changes you want.
Alternative, sepia-based, political: