I think he forgot one thing: the spooky scary stage.
But yeah, this is super nostalgic music. For some reason it makes me think of the Atlas stuff from the time.
Now if you want true “complicated puzzle” music, Lufia 2 was king of both:
