To my mind,the Ashkenazy/Sydney S.O. M1 (Exton) is ideal because it comes with the "Songs of a Wayfarer", as well as "Blumine" as an addendum. For far less money, the Ozawa/BSO/DG M1 did the exact same thing, except that "Blumine" was reinserted into its original second movement position. Unfortunately, the Ozawa/DG M1 is now out-of-print. Either way, emphasize following the text to the songs. Then I would try to get them on to the "Resurrection" symphony as quickly as possible. If that sticks, give it a year or two, and then move on to symphonies 3 &4. You could offer the 4th before the third, I suppose. But if you do that, try to whet their appetite for the 3rd. I agree with a point that somebody made earlier: as wonderful as the 4th symphony is, I don't think that I would use it as a starting point. The 4th is too 'erudite', and doesn't make a whole lot of sense without knowing M1 and M3 first (less so with the 2nd).
Unless they're already a big fan of brass, I don't think that I would try to start somebody out with Mahler 5 or 6. "Das Klagende Lied" can be skipped altogether. Once they get to the 6th symphony, they should also hear the "5 Ruckert Lieder" and the "Kindertotenlieder". Again, they would need to follow the text to get the most out of those works.
So here's what I suggest (the short version): burn them a CD that goes in the order of "Songs of Wayfarer", M1, then "Blumine". Be sure to copy the text and liner notes too. Emphasize that M1 is their reward for sticking with the songs. Pique their curiosity by pointing out that "Blumine" was the original second movement to the first version of M1, the so-called "Titan". Making bigger copies of the CD liner notes makes it much easier for people to read that tiny c-r-a-p. That should be a good introduction. If they like it, then quickly move on to the "Resurrection".
