But in an ideal world, everybody would have been older and it wouldn't have been this "teen steam" we got. No Qui-Gon -- Kenneth Branagh as Obi-Wan (older and wiser from the start, like Ewan played him in RotS), Leo or Christian Bale or even Russell Crowe (who, back in 1999, wasn't the megastar he's since become), all who could actually pass for a young Sebastian Shaw. Somebody who was going to be 30ish at the time of Ep III.
And somebody less demure for Amidala. Perhaps Izabella Scorupco or Kate Beckinsale (I'd pair the former with Crowe, the latter with DiCaprio or Bale).
What else? There wouldn't be a Naboo; it would have been set on Alderaan, so we'd give a damn when it is destroyed in Ep IV. Darth Maul would have survived through to Episode III, where Vader would kill him to take his place at Palpatine's side upon a genuine lure to the dark side in a quest for power. The Wookiees and the Alliance heads (esp. Mon Mothma, Dodonna, and Ackbar) would have figured into the plot significantly. And we wouldn't have seen force lightning from anybody other than Palpatine. Preferably against Yoda for the first time.