I completely agree. I think a lot can be preserved if it’s given the right context and the movie is paced well. A far more interesting opening would be an invasion (which we actually get to see the impact of), with Qui-Gon and Obi-Wan sent to Theed specifically to rescue the Queen, rather than to the belligerents to settle things diplomatically.

One idea I had to remedy the problem of them showing up with Jar Jar, could be to have him already be established as their local guide who helped them navigate the city to reach the Queen. By his following canon appearance he’s become a Junior Representative to the Naboo delegation - specifically a (junior) politician intended to bridge the divide between Coruscant and Naboo, and therefore a perfectly sensible person to serve as local knowledge for two Jedi Knights sent to Naboo to rescue the Queen. So, what if he’s already in that role during the Phantom Menace? It wouldn’t conflict with his poor relations with the other Gungans, either, and it would explain him continuing to travel with the Jedi/Padmé party better than just sticking around as he does in the movie. And doing all of this could unlock a trimmed opening that starts on the action where the plot really starts, with the Queen’s street rescue, the hangar breakout, and the blockade attack. That could easily feel like an intro which leads neatly into Act One, the discovery of Anakin - and there are plenty of expository scenes off Naboo which could give the audience that information even once they’ve left the planet.

Edit: Hell, you could even start with them travelling in the bongo then arriving to rescue the Queen, since the characters really introduce themselves to each other then. Then you’d get to see Jar Jar guiding the Jedi through some ‘secret underwater passages’ to traverse the planet without detection from the occupying army, demonstrating that local knowledge.