I've been thinking about how the opening crawl could fix a lot of problems with the PT. It's already been addressed, but the history of the Jedi and Sith could be explained along with the decline of the Republic.
Also, an idea I think I already put forward is to have the separatist group retitled "the Galactic Federation" and for it to be a coalition of warlords seeking to dominate the republic. The reason why it'd be "the federation" instead of the separatists would be that it allows them to be present from TPM onward. They're the threat from day one, not some ridiculously dull trade group.
I've also been thinking about how much could be done with the use of subtitles. Any audience member unfamiliar with Star Wars would be confused as to what the hell the Jedi are, and what they hell the force is.
One way I thought of introducing the Jedi would be to have the subtitled federation aliens discuss them as they board the ship and also make them more threatening characters.
The following is an example of what could be done. What I want to re-assert is the religious nature of the Jedi, and also their legendary status. Make it seem as if people already doubt their existence, even, to make the skeptical tones people talk of them in in ANH seem more reasonable:
(ship approaches blockade)
Qui-Gon: Captain, tell them we wish to board at once.
Captain: With all due respect, the ambassadors for the supreme chancellor wish to board immediately.
Nute Gunray: Of course. The Galactic Federation welcomes all negotiations with the Old Republic*, and we would be glad to welcome the ambassadors.
*Basically the idea here is that the phrase "old republic" had emerged long before the Empire was ever formed, used as a derogatory phrase by Federation members for the Galactic Republic the insinuation being that their time was already over. This explains why the true glory days of the Republic seem like a distant memory even in the evidently short space of time between TPM and ANH, because we actually aren't seeing those glory days at all in TPM. The Republic is already considered old and over, and what was at first an insulting phrase later became one used with nostalgia by galactic republicans in the new Empire as Obi-Wan does in ANH.
(Later, after Obi-Wan and Qui-Gon talk)
Nute Gunray: What? Speak up, droid!
TC-14: The ambassadors for the Galactic Republic appear to be Jedi Knights.
Rune Haako: Jedi Knights? Religious fanatics! We cannot trust their kind!
Nute Gunray: Indeed. I will contact the master, you may deal with the Jedi however you like.
Rune Haako: However I like? That's unusually harsh of you ... (to TC-14) prepare the battle droids.
(Later, to Palpatine)
Rune Haako: The ambassadors are Jedi, lord. But their ancient superstitions will surely be no match for our-
Palpatine: Viceroy, I don't want this slime in my sight again. This turn of events is unfortunate. We must accelerate our plans. Begin landing your troops.
Nute Gunray: And what of the Jedi, lord?
Palpatine: Kill them immediately.
Nute Gunray: With pleasure, my lord.
(Nute Gunray, as a hologram)
Nute: The toxins should flush them out. Prepare for battle.*
*The original line "they must be dead by now, destroy what's left of them" but sending battle droids to eliminate the remains of Jedi is...pointless.
(Later, as Obi-Wan and Qui-Gon fight and Gunray discusses the situation with another Neimodian)
Neimodian: You misunderstand the Jedi, viceroy.
Nute: Why? Because I don't believe the legends? Seal off the bridge!
Neimodian: The legends are true, sir!
Nute: And more droids! For your own sake, do not fail me!
Neimodian: Surrender is still and option...
(As Qui-Gon penetrates the blast door)
Neimodian: You see? The force is with them!
Nute: It can't be! It's a myth!
Neimodian: You've doomed us all...
(Watching from the screen in the control room, after Qui-Gon and Obi-Wan are forced to flee the scene)
Neimodian: Now do you believe the legends, sir?
-Conveniently, Nute nods to what the neimodian is saying at this point, I think.
That's just some ideas off the top of my head. I know some of it seems probably a little forced, but it's at least introductory and not just ramblings about droids and "this is impossible" and "oh no" and such.
On a completely unrelated note, can I suggest that the strange bubble-view screen of theirs be changed into the kind of screen used by Vader in ESB? It'd be a nicer tie between both series and be less gratuitous than the Windows Movie Maker style bubble-vision device.