pe7ouill3: The blacksmith is at the top of the cliff directly when you come from the northern part of the forest. Normally you have to pass it, there's no way you're gonna miss it. He's gonna talk to you and tell you you're being followed. But in fact there is a bug, nobody is following you, so you just have to wait 30 minutes in the game (30 seconds IRL) and talk to him again.
Found him, thank you. My problem was I entered the shore from the harbor and when I finally discovered this upper entrance, it was probably too late into the night for the smithy to appear.
Fishgius: Thanks for all the answers! As I was playing today, another question popped up: I did the "Smithy's Work" quest where Rolo took away my suit of armor for 6 hours in order to "improve" it. However, I didn't notice any improvement. Is there any? I expected I could finally run or jump in the armor, but it seems exactly as slow and cumbersome as before...
Alaric.us: Yea, this one is weird. The first improvement seems to do nothing. I suspect you should not be able to run in it initially, and it should be adding that ability. You also get another improvement later in the game, which allows you to run faster while spending stamina. Perhaps the first improvement is needed to unlock the possibility of the second.
Got the second upgrade. After it, I could sprint and jump like not wearing it at all. Great! Then I changed to another costume and when I changed back to the armor, sprinting and jumping was gone. Maybe a bug?