Roc, a bird so huge it can swoop you up and drop you onto nearby hazardous terrain or a trap, or if neither is around, just drop you for some minor fall damage. To avoid the difficulty of adding a “you are being carried by a monster” game state, this should happen in a single turn.

Possibly it should only generate only on outdoor levels, or else be unable to use its pick-up attack on a normal dungeon floor.

There should be more birds in NetHack, particularly weird ones which could have nonstandard AI, such as peacocks, birds of paradise, and Canadian geese.

Add giant ravens, a stronger and more threatening counterpart to the raven, primarily so the raven-pacifying side effect of wielding a bec de corbin will be more relevant.

Add vultures, primarily to give druids a wildshape target that is a carrion-eater, meaning it can safely eat corpses of any age. Possibly, the druid or draugr starting pet could be replaced with a vulture, and if so it should have two additional growth stages: condor and giant condor.

The “falconry gloves” random glove appearance has some side benefit involving training pet falcons (or possibly all birds) to attack your foes.

Magpies, a bird that has a stealing attack; unlike monkeys, the stealing attack is limited to shiny objects (possibly based on their material) that are under a certain weight. Under that rule, rings, gems, and amulets are common targets of theirs. They probably have a rather fast speed, too. They should likely generate in small groups.

Magpies would have an alignment of 0 and lack the M2_HOSTILE flag, and thus may be peaceful to neutrals, but angering one makes all other magpies angry as well.

Bird pets are better at combat than mammals, but can carry much less due to weighing less.

Phoenixes: birds with fire resistance and who may automatically resurrect on death, or else revive from their corpse/ashes similar to trolls.

Thunderbirds: birds with lightning breath.

Rocs: large, rideable, fast and powerful birds.