Paul, by a country mile. The only thing about their rivalry which just didn't satisfy me was Paul's Sinnoh League team, and the fact that Infernape got one victory too many in the battle.
Gary was fun but definitely reeks more of the Kanto era writing. He always felt like more of a caricature than a character, and his development was pretty lacking. He worked as a rival for Kanto-Ash, but he wouldn't do the job nowadays.
Barry was a good laugh, but he drew the short straw in terms of being a true rival. He was a fine addition, but having Paul eliminate him in the end was a smart move because Ash beating him again would have meant very little by that point. Conway was a far tougher opponent.
I'm reserving judgment on Trip until we really know where things are going with him. He was really underwhelming as a character at first and in his first couple of appearances he was overpowered, but nowadays I do look forward to seeing him again when he shows up, because we at least get some good battles out of him. Paul was just a hell of a tough act to follow- as far as I'm concerned Paul was one of the series' best original creations and I wish there was a rival akin to him in the games.