First, I don't think that's the most prominent subtextual theme in the PoA story (book or movie), and second, I don't think that it was something the previous two stories had been silent on.
In short, I think that Chamber of Secrets is the HP book so far that has dealt most obviously with the adolescent discovery of sexuality, while Prisoner of Azkaban dealt most prominently with questions of paternal and filial love. The other themes are present, but I think those are the most prominent. (PS/SS, I think, dealt with friendship and acceptance most, while GoF dealt with self-confidence.)
I'm going to ignore the Freudian snake-in-the-pipes business, partly because it's crude, but mostly because it's a bit more modern than this sort of story suggests. The snake has a fairly ambiguous history as a symbol, associated both with masculine power and feminine mystery throughout history, and honestly, given the rest of the context, I'm inclined to think of the basilisk, like Nagini, as negative feminine rather than as a masculine symbol.
The Chamber itself is full of traditionally feminine imagery--it's underground (and underwater), dark, mysterious, damp... it's the ultimate yin space, to use feng shui terminology, and at its heart it contains the consuming monster, the basilisk, and its prisoner-by-fascination is the immature feminine Ginny Weasley.
But even before the confrontation in the Chamber, the book has started to examine the issue of Harry's discovery of the secrets of girls and women. After the Dursley prologue (which involves a punishment from Aunt Petunia and a run-in with Mrs. Mason), he goes to the Burrow, where he has a confusing encounter with the powerful Mrs. Weasley, who is both constantly nurturing him and haranguing her sons for their misbehavior. Her word is law in the Burrow, and she runs... well, not hot and cold, but different varieties of hot.
He also encounters Ginny's crush for the first time. The last time he saw her, she was just running alongside the train. Now she's terrified of him and blushing and hiding from him. This simply puzzles him, and he assumes that he's done something wrong, probably because it hasn't occurred to him that someone would like him that way.
The crush theme comes into play again with the introduction of Lockhart, over whom all the witches dote, much to the consternation of the wizards, who just don't get it at all. His continued presence makes it impossible for the reader to ignore the crush context, even while Harry is assiduously doing so.
A further example of Harry's initiation into the world of the opposite sex is Moaning Myrtle, who keeps a guard on that deepest of girls' mysteries: the girls' bathroom. The overemotional, "distraught" Myrtle disturbs the young girls as well--only the resigned Hermione and the possessed Ginny go in there. (Not apropos of this particular argument, but I've always noted that Myrtle ends up dying in a scenario very much like the one in PS/SS, where Hermione has gone to the girls' room to cry because of being ridiculed, and is attacked by a monster.) The bathroom is also the entrance to the Chamber of Secrets, the deeper level of mystery.
Myrtle also plays into the repeated crush motif, of course, with her giggling invitation to Harry, that, in case he dies, he can share her toilet. Harry, in his typical fashion, is polite about it, even though he doesn't necessarily "get it." But the connection between Myrtle's crush and death is another thematic cue--Harry is entering an initiation as he goes into the Chamber, and he will come out of it with considerably more experience.
Ginny's possession, of course, is a seduction of sorts, for which she is far too young.
Ron's crush on Hermione also becomes apparent in this book first, with his defense of Hermione in "Mudbloods and Murmurs," which is followed almost immediately by the first appearance of the voice in the walls.
There is, meanwhile, the question of the wands. Ron's broken wand is a leitmotif throughout, and when Harry arrives in the Chamber, Tom is able to very easily wrest his wand away from him. Nevertheless, Ron's malfunctioning wand ends up solving a large plot problem (and destroying itself, after which it is replaced by a better-suited one), and Harry's lost wand is replaced by the more grown up (but also quickly returned) sword of Gryffindor.
At the end, Ginny is returned to her pre-sexual state and Harry carefully returns the sword to Dumbledore--it isn't time for any of this to be played out yet. But I would argue that it is in this book when the characters begin to discover the (often scary) secrets of sexuality.
The issue of sexual discovery takes a back seat in some senses in PoA, in favor of looking at Harry's identity as a man. The prologue features a conflict with Uncle Vernon rather than Aunt Petunia, though it is played out through Aunt Marge (who insults his father). In the Weasley section, it's Arthur, rather than Molly, who gives Harry important information. And on the Hogwarts Express, Harry meets the first of many adult men who show him visions of possible futures.
I think the playing with time in the book really helps establish this theme. While Trelawney's predictions are (mostly) bunk, the repeated notion of looking into the future plays out through most of the story, right up to the end, when Harry literally sees a future vision of himself.
Harry sees many different kinds of men in the course of Prisoner of Azkaban, different modes of being a man. He sees Uncle Vernon, the conventional bully, and the teenage Stan Shunpike, a working stiff who hasn't gone very far in life, contrasted with the ambitious teenage Percy.
For the major adults, he sees:
Arthur: The pater familias, wanting to keep him informed in order to keep him safe, understanding what boys are likely to do and having faith that he can handle the information. Arthur is a non-threatening role model, and a healthy one, but Harry always thinks of him as Ron's father, a step removed from him. He's also a bit ineffectual and out of the loop, which Harry can't afford to be.
Dumbledore: The wise old man, knowledgeable about life, experienced in Harry's heroic path, part of his world. But Dumbledore is distant and too large for Harry to feel an identity with.
Cornelius Fudge: The man who would have the most appeal for someone like Percy has none at all for Harry, who's pretty much unimpressed that the Minister for Magic has personally come for him. (Surprised, yes; impressed, no.) He's a symbol of vacuous secular authority, as opposed to the kind of deep power that Harry is associated with.
Hagrid: Harry's friend, the symbol of the outdoors, pure masculinity... but already, by the time Harry is thirteen, in a position of being protected more than protecting. Hagrid is a perpetual child to Harry, and not a viable model of adulthood for that reason.
All four of these men are outside of Harry's ideas of himself as a man, but there are four more men from Harry's past, who are also part of his future.
Remus: Remus, of course, is the one with the most "page time" in PoA, despite the title. (Remus is a prisoner of sorts as well, of his disease and his past.) He is a gentle, urbane man, well-educated and often wise... but unwise as well. The most Dumbledore-like of the younger people, he's still accessible and fallible, a viable idea of a man that a young teen could look at and think, "I could be that." (In my opinion, it's also Remus who Harry most resembles in personality as well.) Remus is a teacher, a talent which Harry will later manifest, and he is a listener. All of the men appear as defenders at one point or another, so that's not particular to Remus, though of course he also appears in this context. In all, his is a model of a gentleman, and something Harry highly desires, I think, but his infirmity is terrifying, and symbolizes something Harry fears in himself--he, after all, repeatedly believes that he could be a monster.
Snape: Not Snape's first appearance, but his first as a fully formed character with a real past. Snape is a bitter, lonely man, nursing old grudges. This is hardly an alien idea--Harry has been neglected, bullied, and border-line abused. Angry Harry in OotP isn't unlike Snape, feeling as though he's been treated unfairly and lashing out at everyone. His response to Snape at the end is disturbingly similar to Snape's response to him throughout. He's not a pleasant identity idea to Harry, but he's a viable idea of someone Harry could be.
James: James is the great there/not-there of the series, and the man Harry is seeking inside himself... ultimately, a fantasy idea, as the end suggests--when he is sure he's found James, it's himself he's found. Yet, it remains James for whom he's searching, the idea of the protector who died for him, the strong wizard who looks so much like he will. In a way, all of the other men in the book are avatars of James (ironically, Snape takes over his bully aspect), and form the father figure that Harry creates in his mind.
Sirius: The theoretical subject of the book, and yet another model of manhood. Sirius is obsessively protective and passionate, Harry's single-minded defender. Sirius is a creature of pure heart and emotion, and Harry does incorporate this into his personality as well, fighting to defend Neville, or to retrieve Cedric's body, or to rescue Sirius himself.
At any rate, I suppose that's all I have to say. I just think that the sexual discovery angle is more prominent in CoS, and the identity issue is more prominent in PoA.