Alot of those ideas have been mentioned before, but its good to see them brought up again for discussion! Avoiding too much naboo is important.

I wonder how it would work if the jedi were on tatooine already to retrieve anakin. anakin sort of blackmails them into helping the naboo in exchange for him joining the jedi.

What if Qui-Gon dies on tatooine at the hands of maul, leaving obi-wan to avenge him later on.

Perhaps if it were an extensive edit, with extra filmed elements, the queen could actually be a princess, and there could be an old king added to naboo to be the face of the suffering people. Maybe he dies too in the end. An alternative ending could be the padme's coronation.