My favorite reward I got in game was when my sorcerer finished his draconic apotheosis and my DM let me play an adult brass dragon as my character, with the ability to shapeshift back into my sorcerer when I needed to cast spells. That was really fun for the apocalyptic last few battles.
In my own games, I've given out an enemy's manor house to a player, upgraded with a dimensional forcefield and a sentient AI butler as a result of a good pull on a deck of many things. This came in handy when the party failed to stop a ritual that caused a zombie apocalypse.
I've given out the ability to cast spells through weapon attack, like the PF magus. I let one player turn into a lich after a long quest to build a phylactery (using a custom necromancer class and getting the capstone ability early.) I've given custom potion recipes to an alchemist. I've given special class features early (like a wizard getting Signature Spell). I've let a wildshape focused character learn how to change into certain monstrosities.
My current game is focused on the players gaining rewards via magic items and pacts with supernatural entities. The only classes in the game are sidekick classes, hammering home that the players need to encounter new things to gain new abilities.
