The Cheshire Cat from American McGee's Alice fits this trope very nicely, especially since the last bit of info he tries to impart is that the Queen of Hearts and Alice share the same mind.
King and Toroko from Cave Story; Curly, if you don't save her.
Doubly so in King and Toroko's case, since King and Toroko die at nearly the same time, with Toroko being killed by Quote and King dying as soon as Quote is done fighting Toroko. No matter how long it takes.
In Tales of the Abyss, there's another one as well: the shockingly-appropriately-named Aslan Frings. A Recurring Character, he's a soldier of Malkuth and you have the option of going through a long Match Maker Quest getting him and his Kimlascan counterpart, Jozette Cecille, together. After the war ends, they're engaged to be married, and their marriage is said to be a symbol of the newfound peace between the two countries. Whether you do the sidequest or not, though, he gets killed right after the timeskip, as your first indication that you haven't actually resolved the main plot yet.
Happens repeatedly in Final Fantasy II (to Josef, Minwu, Richard and Cid), to the point where the GBA Enhanced Remake (and every other one after it) had a bonus game, Dawn Of Souls, made up entirely of playable characters who had died (and cameos from other non-playable characters who had also died), and now they're fighting on in the next life. In fact, parts of FFII felt more like a Kill 'em All in a similar vein to death-saturated stories like The Silmarillion.
Tellah in Final Fantasy IV. Though his death was probably foreshadowed as an inevitability by the fact that Tellah's stats never go up (and sometimes decline) when he's Level Grinding. He still manages to Take a Level in Badass giving his last battle all he's got.
Galuf in Final Fantasy V. Though it wasn't as much a practical loss because, upon his death, all his abilities were instantly transferred to his granddaughter Krile, who continued his role in the party as if nothing had changed. Also, his death was remarkably similar to Tellah's in the previous example.
The original AVALANCHE members, Biggs, Wedge, and Jesse, fill this role. They start off as your initial companions (although not as party members) and are given distinct personalities, but are then promptly killed following a botched attempt to save the Midgar slums.
Reddas sacrifices his life to destory the Sun Cryst with the Sword of Kings.
Tai in Gears of War 2 fits this mold. Much of the first act is building up his invincible nature and the second act shows how he survived brutal torture by the locust. It breaks him so badly he kills himself. Benjamin Carmine also fits the mold, surviving through the second act and having Marcus and the others noticeably saddened by his death. This is especially noticeable compared to his Sacrificial Lamb brother Anthony Carmine in the first game, who was killed by a random sniper shot in the first act.
Harley in Digital Devil Saga. Originally the confident leader of one of the six ruling tribes of his world, the arrival of the Demon Virus triggered a general collapse of his entire command structure, not helped by the new powers the virus had given every member of his tribe. The calm leader turns into a frightened child when met for an intelligence exchange meeting and quickly devolves even further into a scared beast - all of it to show just how dangerous the virus truly is for the inhabitants of the Junkyard.
This happens midway through the second game after the shit hits the fan and you start losing party members; just to emphasize that this is a story where Anyone Can Die, Serph, the freaking main character, is the first person to get offed.
Eternal Darkness is loaded with characters who could at least be considered this - within the main cast, no less! The best cases can be made for Anthony and Paul, who get arguably the most unpleasant ends out of the Chosen - and while most of the others' contribute to an overarching cause in a way that's acknowledged in following chapters, the plot significance of theirs is debatable.
In Persona 3, Shinjiro Aragaki was killed off to show just how evil Strega is, and to propel the Character Development of Ken Amada and Akihiko Sanada, both of whom reach a degree of personal resolution and receive upgraded Personas as a result. Given that he's a well-balanced character and that he has his own personal weapon type that you can continue buying until the end of game (quite unlike most temporary guest characters), it can come as a bit of a shock. In Persona 3 Portable, it is possible for him to survive only to end up in Convenient Coma because the plot would no longer work otherwise.
A less obvious example is Chidori Yoshino, the Love Interest for Junpei. The two spend a lot of time together and we learn quite a few things about her, including her viewpoint on life. During her death scene, she uses her powers to help Junpei get the resolve to continue fighting (plus a new Persona, created by fusing Junpe's Hermes with her Medea). In Persona 3: FES, it is also possible to revive her but she'll have amnesia.
Telltale's Game of Thrones somehow manages to do this with a central player character, namely Ethan Forrester, the newly appointed Lord of House Forrester. He is set up to be an important figure in the story, with the player having to make a number of important decisions as him to decide what kind of Lord he will eventually be. Then he is abruptly stabbed in the neck and killed by a bloodthirsty Ramsay Snow.
Kehanni in Nightfall, whose death is the catalyst for General Morgahn's Heel–Face Turn.
To some extent, Rurik in Prophecies, although curiously both he and the dwarves who kill him are forgotten almost immediately thereafter. You finally do end up fighting the dwarves much later in the game, although without mention of them being the guys responsible for Rurik's death.
And while his popularity with the fans is debatable, Yijo Tahn serves the same role in Factions. He goes through a few starting missions with you and is pretty much Togo's other star student...until he gets sent to help the victims of the plague and ends up as an Afflicted.
All the Servants except Rider in the Heavens Feel route. It's a good thing they added about half a dozen characters to the main lineup for this one or we'd be down to Shirou and Tohsaka and no villain.
The protagonists brother in Red Faction: Guerrilla. He dies after the tutorial mission, conveniently after you have explained to him you just want to do "honest work" and "are not a terrorist". His death turns you into one. Not by choice.
Miranda Keyes. This definitely qualifies as a Player Punch also.
And, a little later, Sergeant Johnson gets killed, just to remind you of Halo: Combat Evolved and of how annoying 343 Guilty Spark was there and then rubbing it in your face when you think he may actually be able to redeem himself.
Anyone who's played the series knows Fire Emblem is an Anyone Can Die series. However, Genealogy Of The Holy War gets MEAN with this. Upon hitting Chapter 5: Door to Destiny (Fitting name) you see 2 former party members die to a boss that you can't fight, but the real kick is when you clear that chapter — you're treated to the "Battle" of Belhalla — and the death of not one character, but the death of damn near the ENTIRE CAST. And Now for Someone Completely Different...
During the Virmire mission in the first Mass Effect game, two of your party members become mutually exclusive. There is no way around it, and they'll both insist that you should have saved the other one afterwards. You can also lose Wrex, but that one's avoidable.
The sequel has your entire original ship, several of its crew, and, best of all, you. Later, your ship is attacked again, and nearly every member of your crew is taken. This time, however, you can rescue them.
Mass Effect 3, being set in a galactic war, has several instances of this with your own party members, current and past. Your choices throughout all three games can defy some of these cases, however. There is one unavoidable case in Thane Krios, who's already dying of a terminal disease. He's one of the deadliest assassins in the galaxy, but his only role in the game is to be killed by Kai Leng after a quick one on one duel, thus demonstrating just how deadly and ruthless he and Cerberus can be.
There's also one other choice regarding the Genophage cure where you have to either martyr Mordin to cure the Krogans or refuse to finish the cure and instead kill Wrex after he becomes enraged at Shepard's betrayal of his trust. Plus, Captain Anderson, who's essentially been Shepard's mentor since the beginning of the original game, dies regardless of his/her actions... it just determines whether he dies quickly or manages to have one final poignant scene with Shepard before his death at the end.
Briggs the pirate in Golden Sun: Dark Dawn. Killed by the shadow monsters spawned by the Grave Eclipse, during the mission to rescue his son Eoleo (who then joins your party to avenge him).
Duncan from Dragon Age: Origins is introduced as the mentor after you lose everyone else in your Origin, only to be killed off a bit later, before he can even start acting this role. King Callinead can also be considered this, as long as you don't antagonize him.
In Blaze Union, we have Siskier in route A, Luciana in route B, and Jenon in route C. Each route also has a few sympathetic enemy characters who serve a similar purpose, at least as far as showing the situation's direness goes.
Several of the heroes in Mortal Kombat 9 play a large part of the overall story, only to be Killed Off for Real near the end to show how truly catastrophic the changes to the timeline has become.
Left 4 Dead's Bill was one of the playable survivors in the first game. In "The Passing", his corpse can be found slumped up against a generator, his cigarette still in his mouth and his M-16, which you can loot for yourself, in his hands.
Almost all of the friendly Non Player Characters in Dark Souls end up dying or going hollow, losing their humanity to the curse of the Undead in the ruins of Lordran.
In one version of Ao Oni, after evading the titular monster and navigating through its house, Hiroshi eventually reunites with his friends. As they debate whether or not the creature's real or some sort of Scooby-Doo Hoax, Takuro tries to take charge and tells everyone not to panic. Cue the Ao Oni popping up and biting his head clean off, effectively proving it's more than some guy in a suit.
The While Guthix Sleeps quest in RuneScape has the player recruit a number of NPC warriors to help them stop a powerful and evil mage from achieving godhood. The NPCs are all known to the player, from other quests and skill training. Some of them are ones that the player might contact at least once a day. Out of the eight NPCs that confront the enemy mage, only two survive; one of those only because he is a demon with super healing. It's a gut punch of popular NPC death in a game where such things had previously been confined to one-time NPCs inside their own quest chain.
In Xardion, Panthera (a leopard mecha, thus almost a literal example) is one of the three party members until being killed off during an escape cutscene.
Mark from The Walking Dead sort of just appears between chapters one and two, and just barely skirts above Sacrificial Lamb since he actually does get quite a bit of characterization. Then he abruptly dies just as quickly as he appeared, and is immediately forgotten by the rest of the cast.
In the second season, when Pete was introduced, it seemed like he was being set up to be a major character, as he was the most reasonable of the cabin group, and episode 1 even seemingly ended with a Sadistic Choice between either Pete or his nephew, Nick. However, Pete becomes a Sacrificial Lion because no matter what choice you pick, Pete will die, and Nick will live.