This 3e hate-fest is great and all, but I'm personally much more interested in figuring out a way to include flight from Level 1 in a way that doesn't hose DMs or Players, going forward, than I am in picking apart any given edition of D&D. Clearly, neither of the two extant versions get it quite right for me.
My take on it is that flight is a difficult ability to balance rsther than any hate for 3rd edition. Editions have tended to over or undershoot the ideal balance point. The issue with 4th edition is not that flight is unbalanced as being too good of an options -- it's that there is not a decent version of it available until the mid teens (and the useful versions I can recall off the top of my head require investing in a paragon path specifically to do so).
[It's like half-elves -- you can discuss many issues with balancing a half elef in AD&D or 2E that seem rather odd when the 3.0 PHB Half elf arrives on the scene; the issue is suddenly in the opposite direction]
If you really wanted to do flight from level 1 then you need to make it a non-combat ability. I'd likely do this with a fly skill (ala Pathfinder) with skill checks required to do combat maneavers while flying. Failure by more than a certain amount equals falling (so high level stunts can be tried by low level characters with risk). But I'd make sure that the standard action version doesn't have any risk of a fall by a marginally competent "bird-man".
The pathfinder SRD makes fly a dex skill and a class skill for wizard, sorcerer and druid. It has an armor check penalty. I'd jsut make some actiosn require skill checks:
1 handed weapon attack: DC 15
2 handed weapon attack: DC 20
Cast Spell: DC 15+ spell level
Fail by 10 or more and you fall. Fail by 5 or more and you are dazed next tunr (only a move action). Suddenly flying creatures are using javilins and not bows (nice for flavor). A 12 dex birdman with a first level investment (1 rank PF, 4 ranks D&D) can't fall on a 1 for throwing a spear.
I'd clarify that flying gives either a -5 or -10 penalty to stealth/move silently checks.
Mounts would make sense again. Casters would need to be high level to reliably use fly. Heck, the base PF rules with a DC 15 to hover are already doing nice things . . .
Those are the sorts of approaches that I'd think about making fly work from level 1.