The later LucasArts games were better at this (I bit The Dig without any hints; think I needed one or two for Full Throttle).
The modern era of adventure games really got this right with the puzzles being more direct and the game being more about story telling. The Walking Dead, Heavy Rain and The Wolf Among Us are great examples of this genre done right. Too bad it didn't save Telltale Games, although Quantic Dream's will hopefully be around after their third console release.
Indie games in this genre have been hit or miss. Broken Age started off amazing (good story, puzzles, didn't need hints) but the 2nd part went back to the old adventure game ways with impossible puzzles. Atmospheric games are fared better: Virginia and Far Lone Sail are two great adventure-ish games that are really good storytelling as game.