Indeed, the Phantom Menace still has some promise. One thing I ended up doing was removing Darth Maul from Tatooine, so that the first time the Jedi actually run into him is on Naboo. Cuts a lot of runtime, and surprisingly, the plot doesn't miss him.
It also helps move the whole Coruscant section along as it's simply one less thing for everyone to talk about. All the while, it makes the Jedi seem a little nicer, as they're going to Naboo to protect the Queen, not to use her as bait.