So, I would have made Karate Kid Legion Leader.
Then Matter Lad shows up, w/ Ferro Twins (future sons of Lightning Lad + Saturn Girl!).
Matter-Eater Lad, Wildfire, Ferros, Theena join the Legion.
Matter Lad, Lightning Lad, Saturn Girl,Supergirl, Star Boy, Light Lass, Ferro (good) goes to get Cosmic Boy (calculating full-well that he is in either a different time or dimension.

MEANWHILE: Vandal Savage reappears as a senator of the U.P., and convinces the UP to attack and imprison Legion. During the ensuing confusion, The other Ferro twin goes bad, but in a fight loses his hand to Matter-Eater Lad (unsavory!).
Vandal Savage lodges an ancient piece of Brainiac in Brainiac 5's spine, creating an internal fight, and distraction for the only smart guy to figure things out. Shrinking Violet hides, awaiting the return of the group, but we don't know this because we are watching...

The group first goes to another dimension where Cosmic Boy is the only thing keeping Earth alive, through magnetic energy. Then a dimension containing a Legion of Super-Villains! Realizing this, they return to the proper dimension, and head through time to the true Cosmic Boy, and the Knights of the 41st Century, in a battle with the most evil Time Trapper! Helping them defeat him, the Group convinces Cosmic boy to return, (although the Time Trapper escaped, and developed a hate for Cosmic Boy 'can you say, future plot??') Upon their exit, they drop off Supergirl back in the 21st Century!

Now returned to the 31st Century, Shrinking Violet alerts the team to the disbanded Legion! A great battle ensues, returning everything to normal... Well, almost.

Bad Ferro got away with his screw-on hand.
Lightning Lad lost an arm, (but proposed to Saturn Girl! Who says yes! Fancy that...)
Matter Lad hooks up with Atom Girl.
Legion is back (and since it was dibanded, no longer associated with the UP or Science Police).

And the group goes on to another adventure, where they recruit a child who found the last Green Lantern ring, entangling the Legion in a story that takes them to the dimension that OA retreated to in the past, and Kyle Rayner (Ion) is the only thing keeping it together! Upon return, the Legion has a young Green Lantern!

Thjen we have more villains waiting in the wings--

Ferro!
Time Trapper!
Legion of Super-Villains? Possibly?

Plus, a re-union with Mon-El that may put him on the team for good! (don't worry about the Lead, Brainiac and Matter Lad now can take the time to make the serum before his release)

And Cosmic Boy would have revealed the truth eventually.