Bilbo Baggins was standing at his door after breakfast smoking an enormous long wooden pipe that reached nearly down to his woolly toes (neatly brushed)-Gandalf came by. Gandalf! If you had heard only a quarter of what I have heard about him, and I have only heard very little of all there is to hear, you would be prepared for any sort of remarkable tale. Tales and adventures sprouted up all over the place wherever he went, in the most extraordinary fashion.
The Herald is a person, message, or crystallizing incident that sets the Hero/Protagonist on the path of adventure. They bring the Call to Adventure. If a story's setup is similar to this:
"Nothing interesting happened in The Protagonist's life... until, one day, X stumbled into her world and changed it forever."
then "X" is the Herald. Oh, and you'd better hope "X" isn't also the Big Bad, cause that tends to get messy.
The Herald can be non-human (a newspaper or news report, for examples), but a more memorable force has more impact.
Common subtropes include:
Luna in Sailor Moon; she sticks around to play the Mentor later.
Fruits Basket: When they find Tohru living in a tent on a Sohma land, and insist that she come live in their house. Repeated when it appears she will go back to live with her family, and Kyo and Yuki track her down to insist that she return.
Rukia from Bleach, in a way, as she is the one who turns Ichigo into a shinigami.
Naota's life in FLCL was entirely uneventful until Haruko shows up, trailing traffic accidents in her wake, to smack him in the head with her Rickenbacker bass, turning his brain into an inter-dimensional portal through which robots emerge to do battle. It Makes Sense in Context, you just have to pay attention.
Also parodied in DC Comics with the Scarlet Skier, Herald to Mr. Nebula, a flamboyant Galactus ersatz out to maliciously redecorate the universe according to his own tastes. When the Skier disobeys him, Nebula punishes him by making him wear increasingly ridiculous costumes.
Films — Animated
Nala from The Lion King, when telling Simba what has happened to the Pridelands. This jerks him away from his 'Hakuna-matata' lifestyle and back to his responsibility as king.
That rhyming butterfly from The Last Unicorn. As pointed out under Literature above, the hunters as well. Their conversation is how the unicorn learns that it is supposed to be the last of its kind in the first place.
Morpheus promised to many that The One would return to bring an end to The Matrix. He scours the virtual world for this special person. On finding him, Morpheus sends a cell phone by courier to Thomas Anderson at his desk as a literal Call to Adventure.
In Men In Black, the NYPD officer who would become Agent J chases down a perp who moves much too fast to be human. He eventually corners the suspect on a rooftop... and is told "Your world is going to end" before the guy's irises blink and he jumps to his death.
R2D2 of Star Wars, when presenting the message "Help me, Obi-Wan Kenobi, you're my only hope." Thus begins Luke's journey to find Obi-Wan and leave Tatoonie.
In Willow, Elora Danan's arrival is the start of Willow's journey.
Bumblebee serves this function in the 2007 Transformers movie; a difficult task since he couldn't speak at the time.
"Uncle" Felix in the first Spy Kids movie; he informs them that their parents have been kidnapped, that they are spies, and tells that 'the third brain lives'.
The Death of Rats seems to have appointed himself Susan's personal Herald in the Discworld series. Either that, or he really, really likes swiping her chocolates, and uses warning her of her grandfather's difficulties as an excuse to get near enough.
She also had a Herald in the movie: Merrick, her first Watcher.
Doctor Who did this on a number of occasions, such as in Colony in Space, where a Time Lord gives the Doctor a mission, allowing him to leave Earth for the first time since his exile. Of course, the Doctor himself is frequently in the role of Herald for his many companions.
The Town Crier in Rome is perhaps the ultimate example of this trope. He stands at Forum Romanum reciting the latest happenings in politics and the military, as dictated by whoever holds the power at present, allowing both the citizens and us viewers to follow the events. It's often used with great success to jump from one political/military event to the next, without having to waste numerous scenes on exposition.
Bryce Larkin's e-mail to the title character in Chuck.
John the Baptist fits the announcement function of the herald: "The voice of one crying in the wilderness 'Prepare ye the way of the Lord!'"
Elner of Wisdom in Galaxy Fraulein Yuna (specifically in the prologue of the first game). Anyone who missed that only knows Elner in the Mentor role. (Yuri Cube might qualify in her very first scene in the second game.)
Duncan in Dragon Age: Origins shows up right about the time events conspire so that he catapults the not-yet-Warden into a world of adventures.
The Warden later shifts into this role, serving as the herald to bring their various companions on the path of adventure. Providing they survive Origins, they continue this role in Awakening and Witch Hunt.
Ariane serves as a minor herald in Witch Hunt, kicking off the plot when she was mistaken for Morrigan by the Warden's scouts stationed in the Korcari Wilds, joining forces with the Warden after discovering both are searching for the Witch of the Wilds.
Colette in Tales of Symphonia is an odd case of the Herald having lived with The Hero for years, and her Herald-ness being expected. They were ready to start the journey and were waiting for a sign.
Ingram Plissken in Super Robot Wars Original Generation. In fact, he could be seen as a multilayered example, as not only is he responsible for setting up the attack that drew Ryusei into the war, he was also the pilot of the artificial planetoid Neviim and (re)opened the Earth to interstellar civilization and all the wonders and perils that implies.
In the instruction manual for The Legend of Zelda, Impa was being attacked by a band of Ganon's minions while she was searching for a man brave enough to save Hyrule. As luck would have it, that's when Link showed up.
In The Legend of Zelda: Skyward Sword, while they are flying through the clouds, Link and Zelda get separated by a dark whirlwind, which drags Zelda to the surface. Link is then led to the surface by Fi, the spirit of the Goddess Sword, to rescue Zelda and defeat Ghirahim.
In Tales of the Abyss, Luke's boring and repetitive life was changed when Tear broke into his manor and tried killing his swordmaster. Luke and Tear's magic collided and now the two of them are on the other side of the world.
Buzz-Buzz in Earthbound is the official Herald, but had Pokey not come knocking at Ness's door for help, the adventure likely wouldn't have happened. Paula herself turns out to be the Herald of Jeff, and Ness possibly the Herald for Poo. Maybe. We're not too sure.
A possible inversion, as despite being The Protagonist, this is arguably Shepard's role in the Mass Effect series. Most of the squadmates are clearly a Hero of Another Story, but none of them ever really stepped up until Shepard waltzed in, offered them a place on their crew and gave them the chance to save the entire Galaxy.
Harbinger has his name for a reason: he is the Herald of the Reapers... as well as their leader. It is also his actions that kick off Mass Effect 2 (and, by proxy, Mass Effect 3); everyone thought the Reaper threat had been dealt with for the forseeable future until he showed up.
Likewise, in The Elder Scrolls IV: OblivionUriel Septim VII is the Herald for the Hero of Kvatch, who not only frees the Hero from the prison cell s/he was sitting in, but also hands him/her the Amulet of Kings and charges the Hero with delivering it to the Grandmaster of the Blades before being assassinated, thus kicking off the game's Main Quest.
"The Child" from Scary Go Round heralded great change in order to inspire chaos. This worked due to lack of Genre Blindness: if a small bald child tells you that "Things will change... soon!", people know that panicking is the right thing to do.
Played with in BIONICLE:The Mask of Light. The mask tries to cast its light on Takua, but Takua tilts it with his foot so it looks like it's choosing Jaller. Jaller is then proclaimed to be "The Herald to the Toa of light", but Takua and Jaller know who the "real herald" is. Jaller agrees to go on the quest, but drags the reluctant Takua along on with him. Since it later turns out that Takua IS the Toa of light, Jaller's role as "herald" turns out to be correct.
In Avatar The Last Airbender, Aang serves as a herald to Katara and Sokka, bringing them the Call to Adventure by promising them to find a waterbending master and providing an opportunity to beat up Fire Nation soldiers, respectively. Interesting case in that Aang is the real hero of the story, but Katara and Sokka follow The Hero's Journey more closely. However, Aang's herald could reasonably be Zuko, as his arrival at the Water Tribe village is what forces Aang to begin to accept the mantle and responsibility of the Avatar.
Arcee serves this role in Transformers Prime by managing to blow The Masquerade in a way that drags three human children into the war between the Autobots and Decepticons. And she's not particularly thrilled with it.