Cypher's conversation with Trinity at the very beginning of the movie has three instances, one minor, two major.
His comment "We're gonna kill him, you know that, don't you?" refers to Morpheus' later reveal that adults aren't offered the red pill because their minds are too attached to the Matrix's reality to let go; note his "He's gonna pop!" when Neo is freaking out after the Construct scene and the "potentials" in the Oracle's apartment all being kids.
Cypher comments how Trinity likes to watch Neo, hinting on her being in love with him.
Later, Trinity says, "Are you sure this line is safe?" and Cypher replies, "Of course I'm sure." Later, an Agent says, "The informant is real." This foreshadows Cypher being The Mole.
Neo's conversations with Choi and Mr. Rinehart are chock-full of these.
The former conversation is the first hint at the existence of the Matrix before it's explicitly shown and explained.
Choi: [receives some illegal software from Neo] "Halleluja. You're my savior. My personal Jesus Christ."
Neo: "If you get caught using that..."
Choi: "I know, I know. This never happened. You don't exist... Hey, something's wrong? You look whiter than usual."
Neo: "My computer... Do you ever get the feeling like you don't know if you're awake or still dreaming?"
Choi: "All the time. It's called meskalin. It's the only way to fly. Listen, you look like you need to unplug."
In the latter dialogue, Rineheart says that Neo thinks he is special, and the rules do not apply to him. Pretty much everything that happens in the movie after Neo leaves the Matrix is all about proving to him that what he said sarcastically was totally true.
Rinehart: You have a problem with authority, Mr. Anderson. You believe that you are special, that somehow the rules do not apply to you. Obviously you are mistaken. This company is one of the top software companies in the world because every single employee understands that they are part of a whole. Thus, if an employee has a problem, the company has a problem. The time has come to make a choice, Mr. Anderson: Either you choose to be at your desk on time, from this day forth, or you choose to find yourself another job.
While this is happening, Neo keeps wistfully looking out the window. He's caught between an authoritative suited figure and the outside world, with the window washers' soap dripping down to resemble the Matrix Raining Code, the barrier between those scenarios.
Neo is shown waiting for interrogation on a wall of monitors. We'll see them again...
Morpheus warns Neo that some people are so dependent on the Matrix that they will resist liberation from it. Then Cypher chooses to turn on his allies and return to it.
During Neo's training, he asks Morpheus: "What are you saying, that I can dodge bullets?" Morpheus responds, "No, Neo. What I am saying is that when you are ready, you won't have to." At the end, Neo becomes the One and stops bullets with a mere gesture.
An earlier moment has Morpheus asking Tank about Neo's progress. "11 hours straight, he's... a machine." In the Matrix sequels, Neo's strong connection to Machines outside the Matrix simulation is revealed.
Pretty much everything in the Oracle's talk with Neo, but three lines in particular: "Your next life, perhaps," "One of you [Neo or Morpheus] is going to die," and "Take a cookie. I promise by the time you're done eating it, you'll feel right as rain." The first two are directly connected to Neo finally becoming the One in the hotel during the fight with the Agents; the third implies insertion or activation of the "Prime Program" the Architect cites in The Matrix Reloaded, as his powers start awakening after he eats the cookie.
An incredibly "subtle" bit of foreshadowing comes in the form of Cypher making Wizard of Oz references while everyone else makes Alice Allusions. This shows he is somehow apart from the rest of the Nebuchadnezzar crew, but also can be seen as illustrating a fundamental difference in how he perceives his awakening. While Alice in Wonderland is at its core a story about a girl finding freedom in an otherwise dangerous and confusing world, Wizard of Oz is a story about a girl slipping into a new land in the midst of tragedy, being hunted for something she never asked for, and forced to become a killer, all while yearning to return home, where she awakens with memories of the other world as if they were an odd dream, presumably to eventually forget them.
Locke's dialogue during his council briefing indicates Zion's defended itself against attacks like this before (although the Machines have never launched an attack on this scale). But, it does seem a little odd that despite a century of warfare, the Machines haven't gone all out against Zion until now. On the first watch, it seems that the Machines simply weren't taking Zion seriously. This makes sense, as they're a pitiful minority of humans who're hopelessly out-manned and outgunned. Initially, it seems like Morpheus was right and that the rebirth of the One has turned the tide and the Machines now view them as an existential threat. However, on the re-watch, it's a clue that the Machines need to leave Zion be until the One's emergence signals the endgame of the current Matrix cycle.
While taking Neo to meet with the Oracle, Seraph specifies his purpose is to protect that which matters most. But if you stop and think, this doesn't make sense. Shouldn't it be the other way around? Shouldn't protecting the One be more important than protecting the Oracle? It's another early clue that the One's really just a pawn on the Machine game board. It also is a setup for Revolutions and the reveal there that the Oracle's the Queen on this chessboard and is playing for the highest stakes: to end the War for the sake of both Machinekind and Humanity.
Serpah's dialogue during this scene also establishes the Oracle has enemies inside the Matrix, setting up the Merovingian and his private war with her. This also establishes she must be a very important Program, setting up the later confirmation and revelations from the Architect.
Regarding earlier versions of the Matrix and the One, which Neo learns about officially from the Architect.
Because of the way they're disguised in plain sight as throwaway lines, many viewers and Neo himself miss it when the Merovingian says twice, with no cryptic language whatsoever, that Neo has had "predecessors" (during the table conversation and after Neo battles the Merovingian's henchmen). This is not only a major reveal in itself but foreshadows other reveals Neo will learn when he meets the Architect later.
Persophone mentions that two of the Merovingian's henchmen are from "earlier versions of the Matrix".
As the Nebuchadnezzar and Vigilant crew are deliberating their plan to find The Source, Morpheus warns about reinforcements and that "Death can come for us at any time, in any place." Turns out he was also referring to the Sentinels in the real world as well, and the quote is spoken at the same time a Sentinel discovers throws a tow bomb at the Vigilant. No points for guessing what happens.
And if you want some unsubtle foreshadowing, notice how both versions of Vigilant captain Soren wear red clothing.
The Architect tells Neo, uncharacteristically directly, "She [Trinity] is going to die and there is nothing you can do to stop it." Neo proves him wrong minutes later... but it turns out he's only delaying the inevitable.
When Tiffany is introduced into the film, she's initially seen alone. But when Tom approaches her, her two children appear. When Tom and Tiffany continue speaking, her husband shows up. And when Tiffany lingers, her husband says that they need to pick up a third child, showing that this iteration of the Matrix is doing everything that it can to keep Neo and Trinity apart.
Thomas Anderson's business partner repeats some of Agent Smith's lines from the first film under the guise of simply enjoying said lines. He's later revealed to be Smith himself, reborn.
The whole game development team dresses primarily in blue, with one exception: a woman who wears mostly reddish colors, who is later revealed to be Sati.
Part of the reason the Human forces had trouble finding Neo is that the Machine World altered his DSI (Expo Speak Gag for "appearance"). We first notice this in a Freeze-Frame Bonus during the Hard-Work Montage while Thomas Anderson labors over the 4th Matrix game: in one of the shots of him taking his pills at the mirror, his reflection is of someone else.
Tiffany thinks that she looks just like Trinity, but her husband finds the idea laughable. We are led to believe that the husband is just being an asshole, but it's later revealed that her DSI is altered as well. (There's another Freeze-Frame Bonus of her reflection being a blonde woman.) So to the husband, she really looks nothing like Trinity.
Also in the above scene, Tiffany expresses how angry she was at her husband laughing at her, going so far as to say that she wanted to kick him hard enough to "knock his jaw off". At the end, Trinity does exactly that to the Analyst — the entity most directly responsible for keeping her from being Trinity.
