Flying in not something fantasy does? I would think, short of Scifi, Flying is mostly a fantasy thing.
Spell casters in most systems have fly/levitate spells
As you mention Pegasys, Dragons and lets not forget demon and the like all tend to fly in fantasy. While having a race that could fly with no form of wings would seem very silly, adding a race that has wings( personly I like bird wings, but bat or insect work too ) would seem very fantasy like.
The problem most people have with flying in RPGs tend to be based on the unfare movement and combat advantages. If you examine movement when it matters, it\'s not a real problem. So they can navigate terain that pose problems to others. They tend to be very vulnrable while doing it, I mean getting a arrow in a wing over a lava pit is a tad more serious than taking one in the leg next to a lava pit. Another issue, mostly from GMs, is that a flying character can circumnavigate important encounters in a adventure. Again I find this not to be that true, all you have to do is give them a reason to deal with an encounter. I mean really, just placing a encounter out there for no reason is really bad plot to begin with. In my 20 years of DM/GMing I have had flying races available to PC for 15 of them. I have never had a game suffer problems because of their ability to fly. While table top PnP RPGing is not entirely the same as Computer RPGing, I find the concept of implementing a workable flying race in a computer based game less of a problem than in PnP. Why? Because we have a 3D visual representation of the world, and that in its self seems to scream to me, USE THE Z AXIS PEOPLE!
Here is my rundown on how I would ... err ... balance ... yuck.. a flying race:
1) Reduce carying capacity, yet allow them to hit as a normal human.
2) Reduce defensive values when in flight, while hitting a flying target is a bit harder than hitting a motionless target, in this case the target is marketably larger ( we assume due to wing span ) and less maneuverable vs. incoming attacks.
3) Limit flight time to mear seconds at a time. Its not easy lofting 100+ lbs of body on two wings. So yes you can fly over the river, to that boat or on top of a building, and do all of this at 2 or 3 times base land movement, you are not going to fly everywhere.
4) Restrict armors to those made specificly for flying races, not a big deal since reduced carying capacity would also limit armor choices.
5) Increase the damage taken from certain attack types. i.e. Crushing for hollow bones, or maybe even fire for feathery wings, etc.
The neat part of all of this is that its not that dificult to implement, nothing listed is super complex, and all could be done a game. I would think all these variables would exist anyway for races, as they are comon to any fantasy race in one way or another.
as far as Im concerned make the races totally useless in combat, I can garauntee people will still play them. Not because of their unbalanced nature, but because some people just want to fly. ( Im one of them )
