There is one golden rule I use when I want to make a good puzzle experience.
Now, there are a many many articles on the subject of how to make a good puzzle. If you're looking for a succinct and yet in depth answer to the question I recommend the excellent blog by at Post Curious here.
I would like to provide an answer with a single instruction:
Start With A Single Instruction
Keep it Simple. If you want to create a mysterious, engaging, and satisfying puzzle experience then no matter what, have the first step be to follow a single instruction.
There is nothing more frustrating for me than to have the excitement of beginning an experience only to be met with a 10 - 15 minute overview of how to play. This is where video games give us our best practise: give your players a tutorial.
Find the Key. Let your players discover the rules, mechanics, and world of the game one baby step at a time.
While it may seem obvious to you that the cipher for the code can be found by counting every fifth letter of the code, it won't be to your player.
Start by having your player find an item. When they do have that item give them a slightly more complicated instruction.
Read the letter to discover the cipher. Once they have successfully found the key you can introduce a further layer of complexity. Remember we must learn to crawl before we can walk.
Solve the Cipher to Locate the Coordinates. So long as you keep your experience simple at the beginning while the player is trying to understand the world you've dropped them in, then you can increase the layers of complexity as you go along. This will keep them intrigued, and inspired to continue to challenge themselves. This is how you build trust from a player in an experience.
No one wants to be bombarded with too much information at the beginning. They want to slowly understand the world, be free to make mistakes that won't cost them, and most importantly they want their curiosity rewarded.
The key to make a good puzzle is to make your players feel smart. Make them feel smart by teaching them how to play your experience. And teach them how to play your experience, one step at a time.