Obi Wan and Qui Gon operating both as Jedi; Obi Wan as a Jedi Knight, Qui Gon as a Jedi Master (like the idea of Qui Gon as a bit unorthodox and being a bit at odds with the Council, makes for more interesting Jedi; there's competing philosophies and the Jedi are at a stage in their history where 'the old ways' are being challenged by Masters like Qui Gon).
Have it start out as a diplomatic mission, but don't make the TF guys such a bunch of transparently evil buffoons. Instead, either make them cunning or, and here's a novel idea for a guy who has one of the main protagonists of the prequel trilogy scream "ONLY THE SITH DEAL IN ABSOLUTES!", have the TF guys voicing some legitimate concerns and problems with The Republic; corruption was supposed to be rampant? THERE! Have the TF guys pissed off about HOW that corruption is damaging not only to their business, but also to commerce throughout The Republic on the whole; graft, patronage, 'special favors' from Senators on the take to the highest bidder, conflicting trade regulation for different syndicates or guilds or what have you.
Truth be told, from what I've read of them in EU literature, Duro and Corellia were the two largest space faring cultures in The Republic and, as a product of their prodigious starship construction, had become massive commercial trade powers. Here's where Lucas should have borrowed from an EU source and made conflicts between two rival trade organizations (one headed by Corellia, the other by Duro) as the flashpoint for conflict.
Instead of having Padme as Queen of Naboo, have her as the daughter of some Viceroy from Corellia. Keeps the nobility and high value target factors, ditches the whole elected Queen crap. Have Palpy be the head of the Corellian delegation to The Senate (which would tie in NICELY to Corellia being the Empire's warship farm in TOT) and have him SUBTLY orchestrate a shooting war between the Corellian led federation and the Duro led federation...and then let both sides suck in Status Quo Loyalists and Anti-Status Quo Secessionists. KEEP IT GRAY as to 'who's right/who's wrong' and create a nice symmetry within the story between the political divisions within the Republic and the philosophical differences within the Jedi Order.
Give Obi Wan and Qui Gon a good reason to evacuate Padme from Corellia; either a foiled assassination attempt or, better still, a successful assassination of her father, the Viceroy. (This would make her the Viceroy, for the sake of simplifying things and the assassins failed to get both her AND her father in the attack.) At the same time, make it ambiguous as to whether or not Duro was really behind it...
Off to Tatooine and hiding out in The Outter Rim, rather than broken down spacecraft. Have C3PO and R2D2 as Padme's droids. They're going for the ride.
While on Tatooine, hiding out and trying to figure out what really happened on Corellia, have Obi Wan meet a young tech/mechanic/pilot by the name of Anakin Skywalker. Make him around Luke's age in Episode IV. Have him living with his brother in-law, Owen Lars, and give them some depth to their relationship and how they don't always see eye to eye. (Y'know, ACTUALLY make Luke a blood relation to Owen and Beru. Beru is Anakin's sister.)
Owen's a farmer, Anakin makes his money as an aircraft/spacecraft mechanic in places like Anchorhead and Mos Eisley, has a T-16 (or precursor craft) that he uses for odd jobs, from carrying mail and small cargo to the outlying settlements and vice versa, transporting the occasional fare and racing.
Anakin makes most of his money doing the other jobs, but is really becoming a hell of a competition pilot for some sort of high speed airspeeder circuit.
Enter Obi Wan, while looking for information on the local goings on and have him meet Anakin. Give them a good reason for Anakin to give Obi Wan a lift in his airspeeder and even better reasons for displaying his incredible flying skills.
"When I first met him, your father was already a great pilot. But I was amazed how strongly the Force was with him."
THERE! Make that statement from 'Jedi' make sense! Oh wait, THAT WOULD!
Have Obi Wan speak of the matter with Qui Gon. Then, have an airspeeder race where Qui Gon gets a good look at Anakin's skills but also a good feel for how strong The Force is with him.
Anakin meets Padme, yadda-yadda-yadda, romantic tension blooms between the two as the film progresses, sets the stage for conflict later.
Internal conflict within Anakin.
Moving along, find a good reason for Anakin to accompany the Jedi and Padme from Tatooine to Coruscant.
On Coruscant, have Padme reunited with Palpy and claim her rights as Viceroy, etc... while Obi Wan and Qui Gon argue over whether or not to take Anakin before The Council; Obi Wan believes they should because he believes they have to. Qui Gon has doubts as to how well the Council will handle such a potentially powerful figure and even graver doubts about how training Anakin in 'the old way' may pan out; Anakin's much older than any Jedi candidate in thousands of years and already has formed his own opinions of life and the things around him; he's not a child and it would be nearly impossible for The Council, so set in their ways, NOT to treat him like one. Qui Gon recognizes that such treatment could seriously blow up in The Council's faces. He believes his philosophy of The Living Force and the method he would train Anakin in would be far better suited to such a naturally Force attuned pupil and an adult at that.
Obi Wan ultimately agrees (Qui Gon did train him, after all and he's turned out none the worse for it) and they keep Anakin a bit of a secret...until Yoda and Mace Windu confront them about Anakin.
Here you can illustrate the clash of philosophies with Qui Gon on the one hand and Mace as the more traditional Jedi Master on the other.
Meanwhile, you can give Yoda quite a bit of depth by having him mediate the debate between the two Masters, taking both sides POVs into consideration and pointing out the merits of both Master's arguments.
A conflicted Yoda could be VERY useful for the rest of the prequel trilogy, as it would certainly go a long way towards explaining how Palpy and the other Sith were able to operate under his nose; he's trying to hold the order together, at a time when it's in almost an internal crisis of it's own. Make it known that Qui Gon isn't the only Master subscribing to Qui Gon's new philosophy and other Masters advocating other, non-traditional philosophies.
Throughout this, he's also weighing the arguments of both the traditionalists and the reformers (for lack of a better term) and just which direction The Jedi should proceed in. Make Yoda fully aware of just how vulnerable the internal corruption and erosion of principles within the Republic have made the Republic susceptible to a major upheaval...one that already seems to be starting with the happenings between Coruscant and Duro. At the same time, The Jedi Council is trying to determine just what their place IS in the Republic, especially if the current situation devolves into a civil war.
So Padme has made her claim as Viceroy and is recognized as such. NOW, she needs to return to Corellia as a show of strength.
Have Palpy encourage it and then make a big, moving speech that makes him look good and like a great candidate for Chancellor (maybe even have him spring a previously laid trap for the current Chancellor that allows him to reveal the Chancellor as being guilty of something that either gets him a vote of no confidence or out and outright arrested for corruption or worse) and have Obi Wan stumble into his first fight with Darth Maul, ultimately rescued by Qui Gon.
Both are stunned by the revelation of a Sith, but keep the question of 'Master or Apprentice?' in there. DO NOT MAKE PALPY SEEM LIKE ANYTHING OTHER THAN JUST ANOTHER OPPORTUNISTIC CAREER POLITICIAN WITH GRAND SCHEMES IN THE FIRST EPISODE!
Sure, everybody who's seen the originals knows who he is, but make it a mystery for people not familiar with TOT and subtle enough for those who are to be a compelling view of just HOW Palp became Emperor.
Have Padme and a force of Corellian warships go to some disputed planet (the big bone of contention between Corellia and Duro) for a face to face, with Qui Gon and Obi Wan in tow. Also, with Anakin volunteering to go along too.
For the movie's climax, have the battle split two ways: Space battle (where Anakin, flying as a volunteer starfighter pilot distinguishes himself as both brave and cunning...Obi Wan says in Ep. IV that he was "...a cunning warrior, and a good friend.") between the Corellian and Duro squadrons and a battle on the surface between the Duro forces (and Maul, secretly) and the Corellians (and the two Jedi).
Ultimately, have Qui Gon and Maul break off from the main battle and have their showdown.
Make the fight GOOD, with plenty of illustration of how Jedi and Sith use The Force differently, but also how Qui Gon's use of The Living Force causes overlap between the two.
Maul bests Qui Gon, Obi Wan helps the Corellians win a decisive victory over the Duro on the ground, Anakin helps the Corellians win a decisive victory in the space battle and then Obi Wan takes off after Maul, they have a good fight and Obi Wan wins...by embracing his anger, but channeling it, in a way that Qui Gon has taught him too, to create conditions for victory without succumbing to The Dark Side.
End of the film, have Qui Gon's funeral and Obi Wan tells Anakin that he will train him, meaning at the time that he intends to train him as Qui Gon wanted to train him.
From there, you've set up:
The inevitable love affair between Anakin and Padme.
The inevitable confusion within the Jedi Order that causes Anakin to become disillusioned with both sides of the divide...and pushes him towards something...clearer.
The Civil War, fall of the Republic and rise of Palpatine from Chancellor to Dictator to Emperor and the collapse of the Jedi as traditionalist side with the Republic and reformers side with the Secessionists, thus splitting the order and creating even more turmoil and confusion for someone like Anakin, as the next two films progress, until, ultimately, he's become a Sith in all but name by the middle of Ep. III.
And then he does because he blames Mace and the traditionalists for taking sides, thus plunging the Jedi into their own civil war, even going so far as to blame the schism for the death of Qui Gon and the growing rift between himself and Obi Wan.
That and for forcing him to repress his feelings, which, by that point has created a rift between himself and Padme.
But now we're just getting into ways to improve the whole prequel trilogy.