I don’t know if any mythological monster has suffered from fantasy RPGs’ power creep as badly as the roc.
When you look at bestiaries of folklore, rocs are badass. Dragons? Forget dragons. Aside from two notable exceptions, most of them aren’t even bigger than St. George’s horse. Basilisk? Sic a weasel on it. Chimera? Get yourself a lump of lead and a lance. But rocs? They can carry off elephants.
But since all they are is big birds—no spells or special abilities to speak of—they’re not that scary once PCs reach a certain level.
My answer? Make sure PCs are exposed to rocs before that level. A CR 9 bird won’t scare your 9th-level PCs, but it has a good shot of terrifying your 6th-level ones. Send the roc after them when they’re exposed, or when conditions favor the roc—when they’re on a pitching ship deck, for instance, or a bare cliff face. A roc that attacks in a daisy-filled meadow isn’t scary, but a roc that takes a camel from their train day after day when they’re lost in the desert is a nightmare. And if you decide to give your rocs the Advanced treatment, you can easily give them a fear-causing shriek or a gale-raising wing beat that adds some CR to the encounter without sacrificing the roc’s iconic feel.
If all else fails, put a cloud giant sorcerer on the roc’s back. That’s plenty scary.
In the minaret-spired cities of the South, rocs are a known hazard. But when a roc carries off the Alabaster Juggernaut, an elephant-shaped construct the pasha uses to hammer down the fortifications of his enemies, the despot places a bounty on their heads too large to ignore.
Beren Skyheart is a druid with some limited oracular talents. He reads the future in the entrails of the birds his roc companion catches. Beren is fond of dangerous monsters, excusing even terrible creatures like chimeras and bulettes for their depredations, and he will battle those that hunt them. But anyone who takes up arms against gnolls or hobgoblins earns his respect.
A garuda comes out of the wastes seeking adventurers of noble heart. Roc-riding cloud giants have descended upon the suli city of Harmony, and the residents need experienced warriors to lead the counterstrike.
—Pathfinder Bestiary 236
Also, forget looking rocs up in Mythological Monsters Revisited—they got a single line in the Introduction.
Rocs don’t grow to full size as long as they are animal companions, apparently. So…are druids with roc companions kind souls looking after the runts of the nest...or are they the things stunting their companions growth? Or is it a lifespan thing? Maybe elven druids are the only ones who live long enough to see their rocs grow to Gargantuan size…