Speaking of the Alan Moore story, there's a bit in Superman 423 where Brainiac 5 reminds Superman that back when he was Superboy he learned about the Legion's future.
Is he referring to a story where Superboy meets the Adult Legion? I only remember stories where Superman meets them, not Superboy.
I also wonder where the Legionnaires are coming from in that story.
I think the earliest is after Adventure Comics 351 (because Lightning Lad doesn't have the mechanical arm, unless it's even older and they're from before Adventure Comics 332) and the absolute latest is before Action Comics 392 (Saturn Girl hasn't changed her costume yet).
Perhaps it's after Action Comics 387? That's the issue where Superboy resigns, so it makes some sense that the Legionnaires then decide to pay the last tribute to Superman before his "death". I'm not entirely happy with that placement since Supergirl seems younger in Superman 423, though.
I can't think of another moment where it would make much sense for the Legion to travel back in time to meet Superman right before he "dies".
Any other clues?
I think Moore is leading us to think of Invisible Kid's death at the hands of Validus in Superboy #203. The legionnaires who came back are the original three who not only started the Legion but were the ones to invite Superboy to join, Brainy as the logical one to explain things to Superman (and perhaps who figured out how they could help him without interfering with history), Supergirl for dramatic reasons, and Lyle. When Superman agrees with Brainy about him being right about not sharing future knowledge we see Lyle with Saturn Girl in the foreground. His death is certainly an appropriate doom that Superman would be aware of, and of course Superboy appeared many times after with the Legion right up to the Great Darkness Saga so there is lots more he won't tell them such as Chemical Kid's death and Brainiac 5's own period of insanity.
As for when they are from I think I would be picking somewhere even earlier by their appearance, but you do make a good point as to when the Legionnaires would decide "now" in the 30th Century is the appropriate time to perform this "last" visit from Superman's perspective.