Sasuke is in the background of one panel, while Naruto is in classes, before becoming a Genin. Sakura is possibly around, but not shown clearly.
In the first episode of the anime, all the members of the Rookie Nine are seen lined up for the Henge Jutsu evaluation. Sakura and Sasuke are even shown going before Naruto.
Shikamaru and Ino complain about Naruto's mischief causing them to be tested on Transformation, with Shikamaru wondering why Naruto is among the graduates when they are assigned to teams.
In Episode 3, a few of the teachers appear while observing Naruto and Sasuke in the classroom, including Kurenai, who is incredibly Off Model; has the red and white on her outfit reversed, and has a different voice actor for that episode.
One Piece also has the anime artists adding foreshadowing of future characters that appeared in the manga:
Akainu appears in the background of a group shot just over a month after his present design was unveiled in the manga.
Jimbei was shown among the Warlords quite a ways before his proper, physical introduction
Shiryuu's shadow showed up in Impel Down long before his existence is even hinted at.
In both the anime and manga of Eyeshield 21, as Sena wonders what club to join, Monta appears in the background, encouraging people to sign up for the baseball team.
The opening used during the Bount Arc had a Couch Gag which would show a picture of a different character each episode. Sometimes, these include characters that haven't appeared yet. Grimjow, Ulquiorra, and Shinji are examples of this type.
Ishida gets a different cameo, depending on the adaptation.
In the anime, he is shown in art class (sewing) a good six episodes before most of the main characters are even aware of his existence, much less that he's a Quincy.
In the manga, he is shown in the crowd during the Don Kaionji introduction.
An early version of Shinji Hirako can seen in the first chapter's cover art page in the manga. He wouldn't make his official appearance in the series for another 182 chapters.
In anime of Katekyo Hitman Reborn!, Tsuna passes by Ryohei, Yamamoto, and Hibari when he is running to catch up with Kyoko.
The first episode of Detective Conan gives Conan's future first-grade friends speaking roles.
An episode of Urusei Yatsura featured a story in Feudal Japan with the cast playing different characters. Before the story itself begins, the cast breaks the fourth wall to explain what is happening... when all of a sudden Mendou shows up for the first time. When the others ask who he is, he calmly replies "My name is Shutaro Mendou, and I will soon become a regular character on this show." He joins the rest of the cast in the story. Sure enough, Mendou's "actual" introduction occurs a few episodes later without any mention of this.
Yawara! A Fashionable Judo Girl, the anime, has a date story where Yawara goes to the park with Kazamatsuri (who's trying to avoid all the girls he stood up). In the background, we see many different girls at different points. One of the girls is on a boat, but hasn't been introduced yet. Since Yoko Nanda's defining characteristic is her bad luck with men, it works rather well.
The first episode features a new story that features cameos by some of the military characters.
Izumi and her husband make a brief background appearance behind a scene where Winry is at a train station. Even earlier, when Ed is giving a shortened version of their adventures in a flashback, she appears in silhouette when he talks about them getting a teacher. The same scene contains Mei Chang.
Yoki. His first appearance is a brief mention, and it gets properly told (uh...somewhat) in episode 39.
Kimblee also appears in the first episode of Brotherhood; Isaac MacDougal offers to break him out of prison, but he refuses. He doesn't become important until much later.
Maria Ross can be seen briefly in episode 5 before making a proper appearance. Then, in episode 6, while Edward explains that alchemists usually encrypt their research notes, Berthold Hawkeye is shown.
Death Note, where L appears at the very end of the first chapter, but isn't introduced until after the cliffhanger.
In the Fist of the North Star, Kenshiro's girlfriend Yuria, as well as his nemesis Shin, are phantoms of Kenshiro's recurring nightmares/hallucinations prior to their proper introduction in the story.
The first manga has him make brief appearances just after the attack on Hellsing headquarters and during the meeting between Integra and Enrico Maxwell.
The end of the first volume of Hellsing Ultimate has him make a brief appearance, as well as a brief flash of him while Luke and Jan Valentine are discussing their role in the coming events. This appears in the OVA, as well.