The argument for Lemieux over Gretzky, in a nutshell:
1) The eye test. At one point in my life, I would have told you that Lemieux was a better hockey player than Gretzky. He just looked THAT good, on an aesthetic level in my mind with Muhammad Ali, Pele and Barry Sanders as jaw-droppingly, sublimely talented athletes who simply did whatever the hell they wanted against world-class competition. Grace and power in motion, at a level that maybe Bobby Orr could match.
2) The "what-if?" game. I think we've all been around this block a few times already. Gretzky played on a dynasty during his youth, while Lemieux basically carried the Pens on his back and won Cups as soon as they gave him something to work with. Lemieux made Kevin Stevens and Rob Brown into 50-goal scorers. Lemieux was passing to Brown when he reached the 200-point range, whereas Gretzky was passing to Kurri. What happens to those point totals if they swap wingers? Also, Lemieux's longevity was severely affected by injury and by cancer -- considering he came back and dominated at age 40, is it really fair to say he had less staying power than Gretzky?
3) The "Gretzky is overrated" angle. Wayne was the ultimate right-place-right-time story, as the playmaking center on a firewagon team during the highest-scoring period in history. Several of his teammates went on to Hall of Fame careers, and would have done so regardless whether they played with Wayne or not. Had he played primarily in the 1990s, when goalies were larger and more fundamentally sound, and opposing teams were far more willing to take liberties with slightly-built superstars, perhaps Gretzky's numbers come back down to earth a bit. Lemieux certainly never showed a lack of ability to score at will on 1990s goalies and to fight through 1990s obstruction, but Gretzky looked a bit less impressive as time wore on. It's common to hear from fans who were young in the 1990s that they were astonished by Lemieux and underwhelmed by Gretzky.
What the argument boils down to is that Lemieux was simply a better player than Gretzky, a force of nature that went largely to waste due to not being in the right time and place. That if you were drafting a team to win it all, you would be well served to take Mario #1.
^ I hope I represented that argument accurately. I think all the major points are in there.