When ignoring Staraptor, I'm pretty sure Crobat is the best battler that learns fly. It's obtainable early and has the highest speed and second-highest physical attack of all Sinnoh Pokemon that can learn fly. (Honchkrow has stronger physical attack, but it evolves very late and has low defenses)
Pelipper is the best fly slave. It's relatively easy to obtain and can also learn surf.