Honestly, there is nothing really required to remove the Gungans beyond cutting their scenes. You skip the entire underwater sequence at the beginning, and cut immediately to sneaking into the city after landing back on Tatooine. Then cut all of the ground battle sequences and instead jump between Anakin flying, the Maul fight, and Padme getting to the Viceroy.

I had an idea for something similar to what you're suggesting for your edit but never got around to it:

Use this crawl (or something similar):

It is a troubled time across the galaxy. Interstellar corporations have preyed upon the greed that has bred in the underbelly of the Galactic Senate. More and more star systems are finding their rights infringed upon and their pleas for help falling on deaf ears. Corruption is everywhere. On the small planet of Naboo, things have escalated to a full scale invasion. The Trade Federation has taken total control in an attempt to further entrench themselves in nearby systems. Receiving news of the plight of her people, the Queen of Naboo is returning home after an unsuccessful audience with the Galactic Senate. Having been secretly granted the assistance of two Jedi Knights, the warrior guardians of peace and justice in the Republic, she races back to rally her people against the Trade Federation before their freedom and their way of life is destroyed...

Start the film with the Naboo cruiser escaping the blockade - replace planet Naboo in these shots with Coruscant. Following this, Tatooine is mostly unchanged (with the exception of removing small bits saying their destination is Coruscant). Darth Maul can even be left pretty much in tact. They get to Naboo from Tatooine, land in the forest, people from the city show up. Proceed with the rest of the film (again, cutting out the gungan sequences) Possibly insert the scene of Anakin going to say goodbye to Padme from Coruscant after the battle, assuming it takes place on Naboo.