In our world, moas didn't do so well against humans—Polynesian settlers wiped them out in less than 100 years (roughly around the time of the Black Death in Europe). But in a fantasy world they might have better luck.
Meanwhile, uintatheriums are ancient herbivores, roughly looking like a cross between a rhino and a hippo. And while they didn't escape the Eocene Epoch (other large herbivores more closely related to our ungulates displaced them), they might roam the grasslands and marshes of your fantasy world.
Adventurers are aboard a ship whose cargo hold is full of moas. (An intrepid baronet hopes to start a colony on his island.) Midway through the journey a gremlin releases the birds from their pens, and the agitated moas lash out at any sailor who comes near.
Uintatherium skulls are prized by orcs, hobgoblins, and ogres as percussion instruments and ornaments for their battle standards. Adventurers who wish a favor from a humanoid clan chief would do well to bring the warlord a uintatherium, alive or dead.
What adventurers first take to be a mirage turns out to be a moa nesting ground. While they are observing the flightless birds, a gnoll hunting party (see the Monster Codex) attacks the nest and may stumble upon the adventurers as well.
—Pathfinder Bestiary 5 171
If you ever want to see a terrifying bird, check out the cassowary at the National Zoo. It has a flashy crest. It has barbed wing-claws. It has a kick that can (admittedly more in theory than in practice) kill a man. It is terrifying.