The phoenix is a favorite of pretty much every medieval bestiary and book on folklore you got out of your middle school library. The problem for you as a GM is that they’re one of those monsters that are mostly only interesting in theory. In practice, 1) despite being mythological, they don’t actually feature in any myths—there are no good stories about them to draw from—and 2) unless your PCs are über-jerks, phoenixes are just too good and beneficent to fight.
The good news regarding #1 is that firebirds feature in a number of cultures, so if you don’t like the Greek model, you can always look to Persia, Russia, or elsewhere. No matter what culture you draw from, they tend to be symbols of light, renewal, and justice, so quests involving them are likely going feature requests for their aid, use of their powerful healing spell-like abilities or (fireproofed!) libraries, or the retrieval of spell components such as a phoenix’s feather or tears (ideally with the firebird’s permission, of course).
The good news regarding #2 is you can pick up Paizo’s Mythical Monsters Revisited, which has (courtesy of Jesse Benner) suggestions for tricking out your phoenix with a little evil—specifically Corrupted Flames (Su). The other option is to throw PCs at phoenixes due to simple misunderstandings, their own eagerness for profit over proper quest-vetting, or desperate need for more serious spell components (like ashes, an egg, or a limb). Either way, your players will find phoenixes very hard to dispatch.
Fraternal ifrit twins want a phoenix captured—they claim for crimes on the Plane of Fire. (This is not unreasonable, given that the Plane is ruled by lawful evil efreet, chaotic evil salamanders, azer slavers, and theocratic mephits, all of whose customs a phoenix might flout). They seek adventurers who will tackle such a dangerous assignment. In actuality, they are orphaned siblings convinced the phoenix is their mother. Though their evidence is flimsy, they are right: the firebird is their mother, and she abandoned them after a prophecy predicted that her care would produce two great evils. The prophecy was not wrong—whether or not the seed of evil was in them in the beginning, her absence has driven the twins quite mad, and they are determined to make her suffering match theirs.
Foreign travelers soon become inured to the grandiose names favored in the Jade Dominions: the Two Tigers. The Dragon Prince. The Lung-Tien Emperor. So they can be forgiven for their surprise when they discover the Phoenix King actually is a phoenix—one that has ruled for 400 years. As one might expect, this has made Huon a beacon of benevolence and fair rule. But Huon’s nobles have grown envious of the extravagant displays of wealth their neighbor monarchs enjoy. Ever since the Phoenix King forbade export of Huon’s poppy products except for medicinal uses, the nobles have been looking for someone to take care of their fiery monarch—even if it means turning to “Northern barbarians and honorless ghosts.”
It is not known which asura captured the phoenix Comet Hope. It is known that he or she turned the phoenix over to a cabal of demodands for “safekeeping,” and the repulsive creatures were only too happy to have such a pet to torment. A few centuries and scores of deaths were enough to break the phoenix, after which the demodands tired of him. Now Comet Hope is Heart’s Despair, a corrupted phoenix who leaves holocausts in his wake.
—Pathfinder Bestiary 227
Regarding yesterday, Fortooate writes:
I have a stat block sitting around somewhere for an Amphisbaena Phase Spider (a head on either side), and while making it, I found a ‘phase creature’ template from Tome of Horrors that can be added (+2 CR) to any vermin. Phase wasp swarm, anyone?
I really should spend more time with my The Tome of Horrors Complete and my Advanced Bestiary. Egads my to-read pile is big.