based on stats, which i use, and moveset, definatly starly.
when stsrly evolves into staraptor (i know, after staravia*) it can learn a fighting type move, close combat. and if you take starly-staraptor to the move tutor in the survival area, they can learn heatwave!
so, lets say my level 39 starly's moveset is:
heatwave
fly
brave bird
arial ace
(which it actually was in platinum)
it can beat:
grass
bug
fighting
ice
steel
and then when it evoled into staraptor and learned close combat (which it also did)
it could beat:
grass
bug
fighting
ice
steel
rock
dark
normal
so in my opinion, definatly starly.