One hint of how the the legend grew, or the impact of the music simply took time to digest, is that In the Aeroplane Over the Sea was ranked #85 in Pitchfork's original 1999 Top 100 Albums of the 90's. Four years later, they redid the rankings with NMH at #4. The Soft Bulletin, somewhat similarly, was unranked originally (although it had just come out in 1999) and was ranked at #3 in 2003.
First time I became aware of NMH was from the Dupont Circle Olsson's awesome staff picks wall which had tons of insightful recommendations (and barely changed over about 9 years, I think) . . .although the strangeness of the album cover, title and band name put me off for a while despite the Olsson's glowing review.