Gary. The rivalry between him and Ash is just classic. Plus, Gary annoyed Ash to the point where Ash always got riled up, as hourglass mentioned earlier. Furthermore, Gary also "reformed" as well, and is pretty much on good terms with Ash while sharing a strong friendship/rivalry with him simultaneously. It sucks that Gary is relegated to "Pokemon Researcher" so early though, instead of continuing his and Ash's rivalry. But the occupation is in line with Prof. Oak's position, so it's OK, I guess.
Paul is OK, but I hate how he releases Pokemon right and left (something Gary never did). Paul also looks too 'pessimistic', as opposed to Gary who could give you a laugh of two back in the old days... But I'll admit, Paul does create a nice turn for the plot, and his influences on other characters can be interesting to see sometimes... And his training methods do contrast Ash's, causing you to constantly compare the 2 Trainers.
Lastly, it seems like though Gary travels alone (when he's not with his entourage), he's still a part of the main cast just like Ash and company are. Paul just seemed a little too distanced from everyone else... And Paul just makes people unnecessarily mad most of the time, for some reason.
So, despite some interest in Paul's role as rival, Gary FTW!