I think signs are a good idea. Having to go up to a sign to see which area it's leading to would be nice. This would reward the player for reading them in advance, so if you get a quest that requires you to go back to an area, you may already know the path based on your exploration earlier in the game.