In my opinion, one of the best points of TPM is that it shows the Jedi at the height of their strength. I especially like how the Nemoidians are scared of the Jedi on board the Trade Federation cruiser, but I agree that if the scene has to go, then it has to go.
To make Jar-Jar's sudden appearance make more sense, maybe it can be established later that Jar-Jar and Padmé are close friends already from the start, by removing shots later in the movie where the two don't appear to be?
I wonder also if there could be shots of Obi-Wan and Qui-Gon sneaking around in Theed that could be added to the beginning of the queen's rescue. Perhaps from later in the movie, or from the deleted Bongo/Waterfall scene? (I have not seen it myself, though. Got only the VHS of TPM)
Another question:
Would it work to (re-)insert (parts) from the deleted scene where Qui-Gon slashes a probe droid in half just before running for the starship?
I have read reviews of the scene that make it appear that it could explain better why Qui-Gon and Anakin are running.