Just about every Pokemon game will have trainers with Pokemon at a level where they can evolve, but they haven't evolved yet. It's usually done to maintain a stable level curve without overwhelming the player with a bunch of relatively strong Pokemon. Generally speaking, your rival is usually tougher than the average trainer, but I imagine it'd have to do with his Starly knowing Double Team and Endeavor.
In Platinum, his Starly is a Staravia in a few earlier battles (Hearthome and Pastoria) and yeah this thing is vicious. Thankfully, Platinum sped up the game overall, which I imagine would've been a pain in Diamond and Pearl if it spams Double Team enough and Endeavor + Quick Attacks your entire team.
So yeah, that's probably why it was a Starly. In Canalave City, his Starly evolves, and no longer has Endeavor (but it still has Double Team).
