Pegasus comes with Int 10 for your convenience. 4HD + 2LA.
Giant Eagle has the advantage that it scales to Huge at 9HD. That's a serious consideration if you're power-gaming your cohort selection. Crossing the size boundary adds some serious melee bonuses to your creature. 4HD + 2LA. (Note that the giant owl also crosses into Huge at 9HD).
Brass dragon wyrmlings are also 4HD + 2LA, but they aren't really all that potent, and they can't grow beyond their age categories in HD (unless your DM handwaves that, which would be an affront to all verisimilitude).
The pseudodragon is fun, but with a maximum potential of 4HD + 3LA, you're going to need to start stacking class levels on it pretty soon. Suggest rogue.
IMHXP, however, you will find that flying monstrous cohorts are never as cool as you thing they'll be. A non-level-adjusted druid with shapeshifting will do everything they can do, and heal you in the middle of a fight. Food for thought.
EDIT: I purposely listed only creatures with HD+LA <= 6 because the awaken spell automatically adds 2 HD, which can potentially push it past availability as a cohort.