Zelda II: The Adventure Of Link.
Pretty much all the Zelda games do such things, it's what makes them so fun, finding all the secrets. For example, in LA I found purely by accident that taking exactly five seashells to Seashell Mansion gets you a free shell--I just happened to have five when I first stumbled upon the place.