If we're talking about rivals that were really important, let's see. Gary was the first, if only by pure nostalgia, but he did show himself as a strong opponent. Their most important battle was at the Johto League, but even that showed they're in equal terms, with Gary's main advantage being more calm and collected.
I ever saw Paul more like Gary, but more cynical and stoic, taking full advantage of Ash's more emotional nature and not falling on his unorthodox strategies (even copying counter shield, which makes me angry until now). For all his faults, Paul doesn't trust only in his ace, he builds a team to win for all purposes. If he win with them or no is arguable.
At last, Allain is more similar to Ash than the previous two, but more hardened by his journey to be the strongest. While he's not deprived of strategies, he trusts to much in charizard and raw strenght in general. But, if only in terms of power and stamina, he's actually stronger.
Summing up: Paul >= Allain > Gary.
Paul have the edge (heh) in terms of strategy, but Allain (ironically, for Paul) have power to back him up. In fact, I'm postive Allain would give Paul a longer run for his money than Ash ever did. But, I won't enter in the "who would defeat who?", that's enough.