Another option to preserve Otoh Gunga, though more radical and mutually exclusive from the above ideas, would be to have the Jedi visit the city upon their RETURN to Coruscant, failing to convince Boss Nass to help them but at least convincing him to meet the Queen, transitioning then into the Queen-meets-Boss-Nass scenes where she wins him over.
The Ancient Lore actually took this approach, and it worked surprisingly well