Although not technically his first introduction, the first time the audience sees Dokuro in Bludgeoning Angel Dokurochan is when Sakura walks in on her while she's changing.
In Elfen Lied, Kouta and Yuka find Nyuu naked on a beach.
Happens repeatedly in Ai Yori Aoshi with the subversion that he ends up with pretty much the only girl he doesn't see naked... accidentally anyway.
Reversed in Akikan. After Melon appears for the first time, she sees Kakeru, who's just gotten out of the shower. Kakeru is ecstatic that there's a girl in his room for the first time ever, but she magically propels him into the wall. It takes a good few minutes before he's actually wearing something.
In Bleach, when Yoruichi first reveals her human form to Ichigo... she's completely naked. Of course, being a Cool Big Sis, she remains completely calm about it all, and teases him about his panic and embarrassment. His shrieking actually caused his wounds to reopen. A little bit later, Yoruichi repeats this performance, purely to mess with Ichigo.
In Code Geass, while it's not their first impression, the same episode that Lelouch and Kallen are properly introduced to each other, Kallen gets soaked with champagne. She takes a shower, he lends her his clothes, and she shows him her bare body, and the point of her knife. Ironically, she threatened - and nearly attempted to kill - him for something else, and her threat is what exposed her.
In a sense, this happens between Suzaku and Kallen Kouzuki. Although they went to the same school, and unwittingly fought in Knightmares, Suzaku only saw Kallen's fake persona, that of an intelligent, quiet girl who misses a lot of classes due to an unspecified illness. When Suzaku finally sees the real Kallen, a loudmouthed tsundere terrorist, she's showering under a waterfall, naked, and her reaction upon seeing him is to grab her knife and charge. Of course, this time she's up against the one character in the series with inexplicably superhuman reflexes exceeding her own, so the knife doesn't help.
Might as well just refer to her as Serial Showerer Kallen.
November 11 in Darker than Black does this to Mao after both being taking to meet Amber. Mao is appropriately freaked out as November 11 sits in a chair with a smile on his face. Played with, though, in that Mao is a cat.
Akira from Eden of the East meets the heroine Saki while he is naked. In front of the White House, no less.
Happens, censored, in the Galaxy Angel gameverse (with Ranpha in a towel) and the manga based upon it (Milfeulle, hanging upside down from a crane, and her skirt rips).
Miroku's first encounter with Kagome in Inu Yasha was in a hot spring.
Well, she did have a shard of the Shikon Jewel around her neck. And they're — I mean, it's huge.
As well as Keitaro and Naru (not to mention most of the other girls as well) from Love Hina.
An amusing subversion at the beginning of the Distant Finale involved a new would-be resident ending up in the same position as Keitaro and drawing similar reactions from the tenants who joined the kid in the on-site Hot Spring. Problem is that Maeda Ema was female as well.
In Macross Frontier, Ranka first meets Alto while he's in the middle of changing into a Latex Space Suit for a stunt show. Both sides react rather calmly to the situation...at least until Ranka hits his Berserk Button by admitting that she first thought she was looking at a beautiful, topless girl from behind.
In Mahou Sensei Negima!, most points in which main hero Negi begins to get to know his students, it's usually while they're bathing: baka rangers in library island, Setsuna in Kyoto, etc. He usually gets away unharmed, though not in Setsuna's case.
In Midori Days, when Midori first appears on Seiji's hand, she pops out of his sleeve and reveals everything, just about paralyzing him in shock. After Midori hastily covers up, Seiji slips out, "WHY DOES MY HAND HAVE BREASTS!?"
Neon Genesis Evangelion plays with this trope multiple times: The first time Shinji actually interacts with Rei (meaning, she's not a vision out of the corner of his eye or a bandaged mess passing out in his arms), he arrives at her apartment when she's in a towel... and falls on top of her; fortunately, since she's an over-the-top Emotionless Girl, she just deadpans "Will you get off?". When Shinji meets Asuka, wind blows her dress up, and she slaps both him and Touji. And we can't forget the infamous toothpick holder scene on his very first evening living with Misato. I guess this sort of stuff happens to you a lot when you're the show's designated Butt Monkey.
In episode 8 Shinji's friend Touji did this intentionally. He had just dropped his hat and was retrieving it when Asuka, who they were meeting, appeared, and had her skirt slightly blown up. She slaps all three of them and said that's the price for seeing her underwear. Touji responded by dropping his pants and underwear flashing her, saying she paid too much and this was her change.
Asuka got what was coming for her in Rebuild of Evangelion 2.0 where Shinji's toothpick holder scene was repeated, this time with Asuka on the receiving end. And Shinji was present as well. Cue Asuka turning beet red, sprinting across the kitchen stark naked and kicking him in the face. And she had the guts to call him a pervert when SHE ran out of the bathroom naked!
The Alternate Universe manga Shinji Ikari Raising Project subverts the dynamic. Shinji walks into Rei in the shower, but Rei just smiles invitingly and then slaps Shinji, Very hard.
Happens to Ranma and Akane twice in the first episode of Ranma ½, first with Akane walking in on Ranma and then the other way around.
In the first case, both manga and anime make a point of showing how Akane looks down to make sure that, yep, Ranma's a boy. In the second instance, when girl-Ranma walks in on her, the anime repeats the joke by having Akane look down at Ranma's breasts —which incenses her further, because it just confirms what Ranma said moments earlier about being "better built". At least Akane was holding a towel to preserve some degree of modesty, but now she knows exactly what both sides of Ranma look like naked.
Much later on, the scene is mirrored with Shinnosuke, an extremely forgetful boy who draws an outdoors bath for Akane... then promptly forgets all about her (but not about drawing the bath). He heads for the bath (naked, natch) and runs into Akane just as she's climbing out. She slaps him out of reflex, of course, but more importantly, his nakedness reveals the scar on his back, confirming his identity as the boy who saved her life many years ago. It's also significant in that Shinnosuke was Ranma's one and only real rival for Akane's affections.
And the original instance is repeated almost verbatim at the end the manga, as an Akane impersonator walks in on Ranma at the bath, in the exact same pose, no less. He certainly didn't expect what came afterward, though...
Spice and Wolf: Horo is quite naked when she first meets Lawrence and remains thus during most of the first episode.
Tenjho Tenge has a relationship like this when the hero is sent flying through the air to land on a girl as she was exiting the bath. Despite the fact that he literally crashed through the roof, she takes this as a sign that they are married...
In Tokko, Ranmaru meets Sakura in Bad Dreams prior to meeting her in person. She's topless in the dreams for some reason.
To Love-Ru does this with Lala and Rito's first meeting, when she appears naked in front of him while he's taking a bath in an explosion of water. The scene is made even funnier when he realizes that there's now a naked girl standing in front of him when he notices he's holding something soft and squishy.
Although both clothed when they first meet, during their first meeting Index quickly challenges Touma's right hand against her magically enhanced robes. They're ripped to shreds and the poor girl is left without a stitch of clothing on her.
And, from that point on, her (now depowered) robes have to be kept together with safety pins, which actually turn out to be quite useful in a later battle with a summoned golem.
Lampshaded / parodied in the first episode of Daa! Daa! Daa!. Genre Savvy Miyu worries constantly that she's going to be in this situation somehow. Guess what happens.
In Corsair, when Mansour sees Aura for the first time during a rescue mission, she immediately throws off her cumbersome dress and starts running around in what is basically her underwear. He is rather shocked.
In Umi no Misaki, Nagi first sees Karin through the window while she's changing with the curtains open. She's just a bit too used to having an empty house in front of her, as Rinne points out.
In the spinoff manga "Eureka Seven: Gravity Boys and Lifting Girl", the main character Sumner witnesses a lifting competition, a sport in universe which is dominated by men and boys. Seeing the best boarder out there perform beyond expectations, Sumner rushes to the locker room to meet said lifter, only to catch a side view of a woman undressing from the clothes. She is notably pissed and the character turns out to be Ruri, the heroine, who cross-dresses in order to get into lifting competitions.
In Fruits Basket, Tohru first encounters Isuzu in animal form, and when she reverts to human, she's naked. Due to Isuzu being exceptionally pretty (Tohru thought she has a supermodel body), it troubles Tohru even more than with boys.
In Girls Bravo, Yukinari finds a naked Miharu sleeping in her bed.
In Hoshizora E Kakaru Hashi, Kazuma takes a bath in the first episode, and walks into the men's side of the bathhouse when he spots Tsumugi cleaning it. He tries to leave immediately, but trips in the process, and Senka, the owner of the Yorozuyo inn, opens the door after hearing him scream, and gets a good look at his naked body as well. In the next scene Kazuma sulks and cries privately, claiming he can't be married now.
When Kaname first meets Tessa in Full Metal Panic, she's just stepped out of Sousuke's shower, wearing only a towel. This causes Kaname to think that Sousuke's been skipping out on their study sessions to make out with his girlfriend.
Jon, AKA Skeleton Man, was introduced to Tarot's mother this way in Tarot: Witch of the Black Rose. Except that he was the naked one, not her. Not that he didn't see Tarot's mother naked later on, but that's what Tarot is all about.
In the U.S. War Machine, a Marvel MAX version of War Machine from Iron Man. Jim Rhodes, the commander of the titular special operations unit, walks into a locker room looking for "Josephs," one of his new team members. It turns out Josephs' first name is Sheva and is an attractive and very well-endowed blonde. She is completely nude when Jim walks in, and she tells him to "close the door." He stares at her, wide eyed and complies. She then glares at him and says, "From the outside!"
In Artesia, Queen Artesia of Dara Dess meets the Duchess Ilyana of Har Misal in the nude. While having sex with both of her sons, her nephew, and another nobleman. Artesia is unruffled - the Duchess is able to keep a straight face due to her upbringing.
Green Lantern Kyle Rayner first meets his future girlfriend Jade when she shows up at his apartment hoping to stay with him, in spite of having never met or spoken to him. He wasn't home, so naturally she decides to break in to use the shower.
In Les Légendaires: Origine, Danael first met Jadina when she was bathing in a lake, having fallen near due to his ride's stupidity. Jadina was less than understanding and reacted by shooting a magic blast at him. Amusingly enough, despite this violent first impression, they had one of the least violent relationship in the main serie.
Then, in a monolog: “Does this mean that the Princesses will also be naked? Oh, Father above, that’s gonna be fun. Why, hello there, so-called deities of sun and moon. No, I swear I wasn’t leering creepily at your haunches. I can’t even say I know what ‘leering’ means. Is it a type of frog?”
In The Elephant Man, a nurse brings John some food and drops it with a scream when she sees him. From the way John hastily tries to cover himself with a sheet, it wasn't only his face she saw.
In Fly Away Home, Anna Paquin's character accidentally meets one of her dad's friends this way after she gets some soap in her eyes and flees the shower. It's a real squick moment when you remember that she's only 12, and she's understandably pissed off that it happened in the first place.
In Doc Hollywood, Julie Warner's character is first seen by Michael J. Fox when she emerges from a lake where she's been skinny-dipping.
Inverted in The Matchmaker.Janeane Garofalo's character first meets her love interest when she enters the (shared) bathroom and he's in the bathtub.
In Dave the first time Dave meets the first lady he's in the shower. She of course, thinks she's simply seeing her husband.
In Roxanne Steve Martin's character meets the titular Roxanne (Daryl Hannah) when she's locked herself out of her house... naked.
In Wimbledon Paul Bethany's character walks in what he thinks is his hotel room only to find Kirsten Dunst's character taking a shower. However she takes it rather calmly and points him towards the exit.
The Star Trek: The Next Generation novel Imzadi tells how Riker and Troi first met - at a Betazoid wedding, where everyone was naked (including Riker). Troi was the maid of honor and for Riker, it was lust at first sight!
A variation of this occurs in Fight Club. The Narrator first meets Tyler when the latter is naked on the beach making a giant hand. The variation, of course is the Narrator and Tyler are the same person, so their meeting was just a delusion.
In Faerie Wars, Henry first sees Holly Blue naked. Not that she minds much. At the end, she asks him whether he thinks she's pretty.
In Michael Chabon's The Amazing Adventures Of Kavalier And Clay, the protagonist, Joe Kavalier, first meets his love interest, Rosa Luxemburg Saks, when he has to get into his friend's locked apartment by swinging up the fire escape, and ends up walking in on her napping on the couch completely naked. Soon after, his friend pays him ten dollars to draw her naked from memory (the fact that he remembers her vividly enough to do a realistic sketch is a pretty good clue that he'll end up falling for her).
Live Action TV
This is how we meet the eponymous Andromeda in her android form. That, and kicking some serious ass.
Occurs in the Doctor Who episode "Blink" as Larry Nightingale's introduction to Sally Sparrow. (He's drunk, which might be an excuse for his inadvertent pantslessness. And he barely remembers it the next day.)
Used in a flashback episode of Everybody Loves Raymond before the main couple got married. After delivering her futon and (mercilessly) finally asking Debra out, Ray leaves her apartment now believing himself to have left the greatest impression, and being 'The Man'. He re-enters to drop something off, only to barge in on her naked, getting ready for a shower. The rest of the episode involves him worrying about this to his brother, believing himself now to be the Accidental Pervert.
There is a character is Gilmore Girls who Rory meets at college who is known only as Naked Guy for a few episodes after she finds him naked in the hallway following a party. Later there are some romantic episodes between them.
Not the first but second impression: in Lost, while Michael is searching for his son's dog, he starts hearing strange noises in the jungle and decides to run away. This leads him into Sun (whom he met the day before, while looking for the kid), having a sponge bath.
Not the first impression, but pretty close. In the first season of McLeod's Daughters, Nick walks into the bathroom while Tess is dressing. She covers herself with a towel, but doesn't realise until he leaves that he could see her bum in the mirror.
Happens in Seacht with Linda and Joanne, Joanne in a towel and Linda being a Lipstick Lesbian. Oh, and they end up sharing a room.
It would give him a good insight as to what sort of person she is.
On the makeup F/X game show Face Off, all body-painting competitions begin with the contestants meeting the nude models they'll be working with. The models always walk on-stage in the buff to begin with, although they put on robes for the interlude when the contestants are deciding how to paint them.
On The Bill, Luke Ashton is splashed with mud on his first day back at Sun Hill and decides to sneak in a quick shower before reporting to his new superior officer. Said officer DS Craig Gilmore loses patience with Luke's tardiness and comes looking for him. This is the beginning of their Will They Or Won't They situation.
Mythology and Religion
Anyone wondering whether this is Older Than They Think need only think of the fate of Actaeon after he interrupted Artemis while she was bathing (she wasn't so harsh on Siproites). Or Tiresias, when he caught Athena bathing, though he only lost his eyesight. These particular Greek myths are Older Than Feudalism.
In Breath Of Fire III, Ryu first meets Deis when the magic pyramid seal on her is released - she's stark naked. Ryu turns beet red and looks away, but she ends up standing right in front of him to talk to him, and is completely oblivious to his discomfort. Later, it's made rather obvious that he developed a little crush on her because of that.
Gender-reversed in Breath Of Fire IV. When Ryu first appears, he's completely nude, and Nina is right in front of him. Fortunately, a merchant who had fled from the monster that preceded Ryu's appearance left some clothes in a chest, which Nina quickly asks him to wear.
The Exile's introduction to Atton Rand in Knights of the Old Republic 2 is him/her walking into Atton's cell in his/her underwear. Atton will continue to rag on the Exile about this until he/she finds some decent clothes.
Near the start of Lunar Eternal Blue Lucia arrives in the Blue Spire several seconds before her clothes materialize, rather surprising Hiro. She's an Emotionless Girl too fixated on her mission to care.
It's revisited twice in the same game. The first time is an inversion of the trope, with Lucia walking in on the game's protagonist Hiro in a public bath. Since she lacks social skills, she doesn't see the harm in bathing on the men's side of the bath and just wants to be with her friends. Hiro's Nonhuman Sidekick Ruby prevents him from seeing any naughty bits initially by blocking his view, then by clawing his face to a bloody mess. The second instance has Hiro walking in on Lucia bathing along, but by this point in the adventure, she has actually become human enough to be genuinely (and very loudly) embarrassed about the whole thing.
Oddly enough, Hiro drops in (literally, as it turns out) on Lucia once more in the game (and, surprise surprise, no clothes present) at the very end of the game in her sanctuary on the Blue Star. This time, she doesn't seem to mind and is, in fact, overjoyed to see him.
In Max Payne 2 after initially seeing Mona Sax only for a few seconds and thus learning that despite the events from the previous game she is still alive, Max decides to meet her later on. When he finally finds her in her secret hideout she is taking a shower. She is rather calm about this, which enforces her Femme Fatale image and asks Max for a towel.
In Pokémon-X, the main character Brendan meets May by walking in on her in the midst of changing, naked from the waist up, resulting in a love/hate relationship.
Sluggy Freelance does this in the aptly-named "Game Called on Account of Naked Chick."
In Outsider, this happens to the main character: Ensign Alexander Jardin. After the destruction of his ship by an unknown enemy, Jardin wakes up naked and on a medical gurney, with two of the other main characters in the room. As it turns out, he's on board the Loroi warship Tempest, just as Fireblade starts the mind rape. But waking up only postpones the inevitable.
On South Park, the first time Token actually met the new girl, Nicole, was when she came into the boy's locker room as he was getting out of the shower. He was wearing a Modesty Towel, but the two were both embarrassed anyway. (Incidentally, the whole thing was a plot by Cartman to trick them into becoming a Token Minority Couple.)
In Adventure Time, Lemongrab first meets his "companion", Lemongrab 2, when LG 2 walks into the room naked. Lemongrab is confused at first, then intrigued. He walks up to Lemongrab 2 and inspects him, then pokes him repeatedly. Lemongrab 2 responds by poking Lemongrab back. After that, they smile and nuzzle their faces together lovingly. Two episodes after that, the two Lemongrabs are shown to have had children together.
Crawford: One day my girlfriend and her boyfriend and I were sunbathing topless because that's Barbados - you can wear nothing if you want. And the Pepsi guy and my agent to meet us for lunch. I wondered should I put on my top because I have a business relationship with him? I didn't want him to get offended because the rest had seen me with my top off. Meanwhile, a she's saying to my agent "I hope she puts on her top." He wasn't even being a shmuck, like wanting to see. He wanted to keep our relationship professional.
Playboy: Did you or didn't you?
Crawford: I left`it off and it was fine with everyone.
Every single one of you arrived into the world in the nude.
The first time John Barrowman met his partner Scott was at one of his stage performances. Not only was he naked on stage as soon as the curtain opened, but Scott also got an eyeful when escorted to the dressing room of Barrowman, who was still undressed.
When Winston Churchill was visiting Washington D.C. during World War II, Franklin D. Roosevelt wheeled into his room for a chat, only to discover Churchill lounging around naked (as he often did at home). "Great Britain has nothing to hide from the United States," Churchill told him.