Solstice: The Quest for the Staff of Demnos (1990) follows a wizard called Shadax on his quest to retrieve the eponymous staff in order to save a princess from being unjustly incarcerated. The game is essentially a huge isometric labyrinth filled with devious traps and oddball creatures to ensure especially frustrating peril in the absence of any kind of map to help the player. (Well, at least it was like that before the Internet era, but make no mistake: the game isn't by any means easy nowadays, either.) One of the most memorable aspects of the game is its jazzy musical theme filled with deep bass notes uncommon for the NES.
The Solstice any% has had more revisions than most movies on this site. This one improves the preceding version by 1.25 seconds thanks to a new trick and even better optimization. More details can be found in the author's comments.
We also have a 100% Solstice run.