Levitation and flying allow you to untrap falling rock traps.

New object type “boots of burden”, magical boots which increase your carrying capacity by 50% when worn.

A realistic implementation would mean the boots cease to work when you begin levitating or flying even if you are still wearing them, but this may be too tricky to implement given that the carry cap change may need to prevent the hero from leaving the ground in some circumstances, and the game needs to concisely tell them why.

Artifact towel that acts as a magic carpet: invoke it to start flying on it. Doesn’t work if you’re currently wearing the towel, and trying to wear the towel either doesn’t work or ends any flight.

Remove the air currents in Sokoban that prevent you from floating or flying over the pit and hole traps. Instead, apply the normal luck penalty. Though it’s been pointed out that this would allow a player to bypass the entire branch and then negate the whole luck penalty if they can find or create a coaligned unicorn and throw a few gems at it.

A cloak of flying.

Flying is voluntarily controlled, not automatic (i.e. you tell the game when you want to start and stop flying). While flying, you burn nutrition faster.

Valkyries only gain wings (and therefore flying) after they are crowned.

Valkyries can fly at will with the #fly command, but it costs Pw per turn/flying action to maintain.

Jetpacks, a chargeable source of levitation/flying. They are worn in the cloak (or body armor?) slot and grant 0 AC.

Expert-cast levitation, or a blessed potion of levitation, grants flight instead of levitation.

Wind dragons, a cyan D whose breath is a wind beam: it doesn’t damage you, but blows you backward, and can’t be reflected. Their scales grant flight, which now confers resistance against knockback and Newton’s Third Law.