The Internet Archive has collected the first dozen years' worth of Nintendo Power magazines. I was a subscriber to Nintendo Power for the first couple years, having previously received the Nintendo Fun Club Newsletter. The first issue contained an extensive guide to Super Mario Bros 2, teased a game called Lee Trevino's Fighting Golf, and the Legend of Zelda was ranked the #1 game, ahead of Mike Tyson's Punch-Out, Metroid, Super Mario Bros, and Kid Icarus.
The July 1991 issue shows how good Apple co-founder Steve Wozniak was at Game Boy Tetris:
"Evets Kainzow" is "Steve Wozniak" spelled backwards.
Update: Foursquare founder Dennis Crowley made his way into the high score list in the magazine twice in 1990; once for Strider and again for Ninja Gaiden II (alongside Steve Wozniak's massive GB Tetris score).