Maybe we're thinking about this the wrong way. Instead of changing perlihorn's attack, lets switch odor sleuth with fake tears. Boom, now Boatborn wins again. Perlihorn is supposed to be weak at the beginning and weak versus boatborn - I'm okay with this!
Perlihorn will usually beat uncarp, though, because of the higher attack. However, since the cpu can be stupid, it's not guaranteed. (since uncarp is better earlier than Perlihorn, its okay)
Uncarp, meanwhile, will usually beat Boatborn, however, its not guaranteed (because boatborn is better earlier than uncarp)
So balancing both factors you have:
Perlihorn ties uncarp (type bonus vs early power bonus)
Uncarp ties Boatborn (type bonus vs early power bonus)
Boatboarb always beats perlihorn (type bonus plus early power bonus)
Even for the "your rival is the butt monkey" thing, I don't think it's too big a deal - the first fight is solely so the Prof can lecture you about how these things can easily turn lethal. It's not a "real" fight, and there's no actual consequences. That stuff will happen in the SECOND fight.
We could have the rival genuinely concerned about your pokemon's health if he wins, though!
(Or we could simply always have him pick the weaker mon! Hah, inversion!) Instead of ever making it impossible to win, picking boatborn makes it impossible to LOSE. And it really reinforces Boatborn being the "early powerhouse" mon.
I'm actually really really liking this idea now...