In Gantz, Kei Kishimoto arrives at the room naked, having just killed herself while bathing. Let's just say a lot of the guys there were pretty happy with that surprise, and it was quite possibly the reason why the two main characters fell for her.
Tomihime is bathing naked in a lake in Ayakashi: Samurai Horror Tales when we first see her. Everything comes full circle at the end, too: she's also naked at the end of the story.
Chii from Chobits is first seen only wrapped in some bandages that come off when she activates.
Horo from Spice and Wolf is naked throughout most of the first episode, being a mystical wolf-god who has just taken a human form.
Yuria from Yuria 100 Shiki is first seen naked in her creator's lab, and remains so for quite a while. Somewhat justified, as it's hentai, and she's a Sex Bot. She also runs away from him before he has a chance to give her clothes, though it's not likely he would have.
The first time we see Meru Otonashi, Abiru Kobushi, Nami Hitou and Harumi Fujiyoshi in the first episode of Sayonara, Zetsubou-Sensei, they are naked in a communal bath at an Imagine Spot from Kafuka. However, it probably doesn't count since it's only at Kafuka's imagination.
Justified in Zatch Bell!. Zatch went fishing before flying through Kiyo's window, and hadn't yet dressed himself.
Timmain in ElfQuest first reveals herself to the Wolfriders after being presumed dead for 10,000 years by shape shifting from wolf to elf form, naturally without clothing. This doesn't bother her in the least, although she does pay lip service to modesty by wearing Godiva Hair whenever she's in elf form.
In the Siege at Blue Mountain series, Leetah's first appearance is her nude, uninhibited dance with Nightfall. This is given a kind of inverted bookend at the end of the series when she's in bed with the sleeping Cutter, looking naked and vulnerable as she contemplates the future.
Supergirl: One of the more recent incarnations of Supergirl was found naked in stasis in her spaceship, justified as allowing her to absorb more yellow sun energy, making her initially stronger than Superman.
Superman is usually depicted as naked on arrival as well — but that doesn't warrant as many comments as his cousin as he's always a baby coming out of the rocket.
Ditto for Chris, the Kryptonian child Clark and Lois wind up fostering. Possibly because his parents didn't have any way to make him clothes in the Phantom Zone.
The first time we meet Apollo and Midnighter in The Authority they are naked on the floor of an abandoned warehouse, something that is not explained or even mentioned — they just get up, put their costumes on and go out fightin' crime. And yet, some readers were still shocked — shocked, I say! — when they finally realized these two badasses were a couple.
In Transmetropolitan our first introduction to Spider Jerusalem has him completely naked, save for his incredibly long scraggly beard and hair.
In the original Den stories in Heavy Metal, the title characters arrived in Neverwhere as physical ideals and completely nude, but find themselves never needing any clothes afterward.
However in the animated movie (and for the sake of the censors) Den does put on a loincloth because "There was no way he was gonna walk around this place with his dork hanging out!"
Granted, it was a dream, but this is how everyone's introduced to Will Vandom in the comics version of W.I.T.C.H..
In the Uncanny X-Men storyline that introduced the island nation of Genosha, Wolverine and Rogue were teleported there by a mutant code-named Pipeline. Their clothes however weren't.
Not that long after, Rogue went through the Siege Perilous. When she was brought back in UXM #269, readers were shown her body being built up, first bones, then muscles etc. until she finally sat naked on the floor.
In The Blood Spattered Bride, Lesbian VampireCarmilla has a memorable entrance — she's discovered buried in the sand, naked, wearing only a breathing snorkel.
In "Buenos Aires Vice Versa" the main female character is shown completely naked in the first scene she appears.
In the beginning of Dark City, the main character awakes in a bathtub.
Julie Warner's character in Doc Hollywood is first seen emerging from a lake where she's been skinny dipping.
Rufus (Chris Rock) pulls this off literally in Dogma.
Remember Ursula Andress coming out of the ocean in the James Bond movie Dr. No, wearing only a bikini and a hunting belt? In the novel, it was just a belt.
Leeloo in The Fifth Element is shown getting reconstructed from her DNA. After a few moments of PG-13 nudity, the machine dresses her in fashionably revealing bandages.
Mr. Chow of The Hangover first appears naked in both films of the series. In the second it is rather low key, but in the first he jumps screaming out of a car's trunk and proceeds to beat two of the protagonists senseless.
In A Knight's Tale Geoff first appears walking down a road stark naked. In the commentary Paul Bettany laughs about how unusual a way this is for an actor to make his entrance into mainstream American film.
Gorgeous Mathilda May spends almost the entirety of space vampire movie Lifeforce completely naked.
In Overboard, Joanna is pulled out of the water wearing nothing but her panties. She lost her nightgown and robe in the ocean. This could be taken as symbolic vulnerability referring to her amnesia.
The Brazilian film Sal De Prata starts with a woman naked — shown only from above the shoulders, however — explaining why the movie is rated "18+". Oh, and she's having implied sex from out the screen. Anyway, this woman is one of the main characters, and the scene is actually part of a Movie Within a Movie.
From a canonical standpoint, this means anything nonliving. One might question why Terminators don't smuggle clothes in their various body cavities instead of having to go through that "give me your clothes" routine, but watching Arnold literally pull clothes out of his ass would undoubtedly Squick many viewers. On the other hand, only Rule of Funny can explain why the shape-shifting T-1000 also arrives naked, even though its "clothes" are part of its body.
Possible Fridge Brilliance: the T-1000 can't mimic anything unless it's touched it first, so it couldn't take on the appearance of a police uniform until it touched the cop. The bigger question is how it could travel back in time at all, since unlike the T-800, it has no skin grafted onto its surface.
This has been spoofed several times, including by Billy Crystal in the opening sequence to the 2003 Academy Awards ceremony, in which he arrives back in time naked, holds his gut in, then lets it go.
We're first introduced to Maude Lebowski in The Big Lebowski as she's swinging from a harness naked while squirting paint on a canvas.
The Birth of Venus, Sandro Botticelli, c.1485
Friday the Caribbean tribesman in Robinson Crusoe. The novel associates nakedness with savagery, so one of Crusoe's first steps towards "civilizing" Friday is to give him clothing.
Mowgli in Rudyard Kipling's original The Jungle Book is adopted by a pair of wolves as a naked baby, and spends most of his childhood and adolescence naked. Of course this doesn't make him a nudist, because he isn't naked for ideological reasons — it's just what he's comfortable with.
Discworld: Greebo's first appearance as a human. Nanny's reaction? "Cor." Even Granny Weatherwax turns red and starts hyperventilating.
In Sorceress of Faith, the second book in Robin D. Owens' fantasy/romance series The Summoning, the main character is summoned from Earth to a fantasy world while she attempts to work a skyclad Wiccan ritual ... meaning she's bare and embarrassed when she makes her first appearance before her summoners.
Touchstone makes his debut in this fashion in Sabriel. In this case, he's been enchanted into the appearance of a wood statue and stuck on the front of a ship, with his soul trapped in Death. Sabriel has to retrieve him, with some embarrassment on her part. It was done by the Abhorsen of his time, two hundred years ago, to protect the last remaining member of the royal family, bastard or no, until Kerrigor could be defeated. The place with the ships was heavily enchanted against Free Magic and undead power, making it the safest place in the kingdom. Why stripping his clothes, turning him into figurehead, and mounting him on the front of a ship was necessary, no one really knows.
Túrin's first meeting with his Love Interest Níniel is of her lying naked on the grave of the elf who had an unrequited crush on him. He takes this as a sign and later they get married. It's a pity then that she's actually his long-lost sister Niënor.
Johanna Mason in The Hunger Games, specifically Catching Fire. While she is wearing clothes, she then takes everything off in an elevator while casually talking to Katniss and Peeta, presumably because Naked People Are Funny.
Joan Smith, the slightly odd girl encountered in Robert Westall short story Hitchhiker first appears completely naked. She claims this is because her clothes have been stolen.
River Tam in Firefly, which definitely uses the "vulnerability" implication. The entire sequence seems like a metaphor for rebirth; River emerges from a box, screaming, crying, and confused, and immediately adopts a fetal position once she gets out of the box itself, and is naked until Inara, Serenity's mother figure, wraps her up in clothes.
Kyle XY begins, My birth was unconventional at best. My first memory was waking up in the forest. Like a newborn baby, I had no idea who I was or what was happening. My eyes weren't sure what they were seeing. Every sight, sound and feeling was unfamiliar. Every species is born with instincts that ultimately create a balance with nature. Every species except the one I was born into.
Daniel Jackson's first appearance in season 7 of Stargate SG-1, after his de-ascension and just before his return to the main cast. This was so nice, they did it twice: in the season 8 episode "Threads", Daniel ascended again, then descends... in Stargate Command, a room away from the rest of SG-1, and immediately asks Jack O'Neill for something to cover himself up. And ends up using a flag. RepliCarter's first appearance is also naked.
In Doctor Who for "Journey's End" the clone of the Tenth Doctor comes into existence sans clothing. And the fangirls go wild!
Third Doctor — highlights a partial example, at the end of 'Spearhead from Space'. The Doctor talks about how he's landed on his feet... "I came to this planet with nothing but the clothes on my bac— I've just realized these clothes aren't even mine!"
In the Star Trek: Deep Space Nine episode "Broken Link", when the Founders punish Odo by turning him into a flesh-and-blood quasi-human, he is ejected from their Great Link naked.
In the Smallville season four premiere, we see that Clark is flung back to Earth via lightning bolt, in the middle of a cornfield, stark naked. As far as he claims he is Kal-El so it is very much like a birth. As he's in his cold, emotionless Kryptonian mindset, he doesn't seem to realize or care at all that he's naked.
When Xena and Gabrielle arrive in Illusyia in "The Bitter Suite" episode of Xena: Warrior Princess, both are completely naked, having lost their clothes to the rapids that brought them there.
In the Eureka season four premiere, Fargo is in the shower when his cell phone rings. He answers it and gets dragged back in time to 1947.
He also has a short fantasy sequence where he imitates T-800.
In the Sherlock episode A Scandal in Belgravia, when Sherlock and Irene meet each other for the first time, Irene is completely naked. Of course, she does this to render his trademark scan useless against her. (Can't learn anything too important about somebody if they're not wearing any clothes.)
In "The Fountain of Salmacis" by Genesis, based on Greek Mythology, Hermaphroditus sees the nymph Salmacis "in a cloak of mist alone".
In one of her earliest appearances as a model, Cindy Crawford was topless in the March, 1989 issue of Vogue magazine.NSFW She was modeling makeup in the photo. A year earlier she posed nude in Playboy.
Marilyn Monroe as the first Playboy Playmate in 1953.
In Lunar Eternal Blue, Lucia is naked when awakening on the Blue Star, and arrives on Lunar several seconds before her clothes.
Ryu in Breath Of Fire III — once when he's a child and once when he's a teenager. Definitely to give off an impression of vulnerability. Deis /Bleu is also naked at first, both while sealed in a magic pyramid and asleep and after being awakened. She is not vulnerable however, giving Big Guy Garr the beating of his life while berating him. Interestingly enough, Ryu, who himself has many many instances of being Naked on Arrival, is shown to be extremely shy around her, turning beet red and looking away.
Ryu starts off this way in Breath Of Fire IV The first character who he meets after his arrival promptly points him to a box of clothing.
The first time we seen Johnny in Metal Gear Solid, Meryl has just stripped him naked and stolen his uniform, establishing his status as the series' Butt Monkey. Surprisingly, Metal Gear Solid 4ends with the two of them getting married.
Bill Rizer in Contra ReBirth, after waking up from time travel. Brownie helpfully hands him his bandanna (but not pants).
Idea's first appearance in Soma Bringer was naked and curled up in a cocoon.
Broken Saints: While he is not immediately introduced this way, in the first chapter in which he appears, Gabriel Dunn strips down to his skin for his fire-walking trial.
In Sluggy Freelance, the probably-not-robot ninja assassin Oasis is introduced in this strip, producing a phrase that has become the title of an entire book of Sluggy comics: "Game Called on Account of Naked Chick".
Naturally, most of the characters in The Bare Pit qualify, since it's a naturist comic. In fact, lots of people get this impression of Zoot, since the first story arc features him absentmindedly strolling into town naked.
Angora from The Meek appears nude on the front cover of the very first chapter, and runs around nude for some time after that.
Grace in El Goonish Shive comes close, but wears a trench coat because it's the middle of winter.
In Shifters Ferrah ends up in this trope when she arrives in a Mental World after being hypnotized or dominated by a vampire's mental power, though she quickly employs Hand or Object Underwear. Seen here.
Quite a few ournalRoleplay settings feature this, often also having the unfortunate characters arrive Covered in Gunge. Examples include Roleplay/Trans9, where hundreds of people "podpop", and Roleplay/Edensphere, where they break out of cocoons and find themselves to have Laser-Guided Amnesia.
ThunderCats: The first episode has all the heroes naked until Jaga gives them clothes.
The World of David the Gnome: David first greets the viewers while taking a bath. He explains the purpose of the show in this manner until his wife brings him a towel, and then continues his introduction while getting dressed.
In the episode "The Transmogrification of Eunice" of Ben 10: Ultimate Alien, the episode's titular character is found in this manner my Ben, Gwen, and Kevin, covered by Censor Steam.