In Gears of War, Carmine is the first squad member killed. He's also the only one without a unique face, just wearing a helmet. His name is a shade of red, no wonder he's a Red Shirt. His BackupQuadruplet brother shows up in the sequel only to get killed off too.
Lieutenant Kim from the first game also counts, as he had his own character model, and thus actually had a chance of being a reccuring character.
Crysis does this with two members of the player's squad. Aztec dies before you even get a good look at his face, and Jester gets offed by a giant alien squid at the end of the first level.
The way Super Robot Wars: Original Generations was set up, probably Lamia Loveless was turned into a Sacrificial Lamb to add suspense in OG Gaiden. So you get acquainted with her a lot in the OG 2 portion. Then in the bonus segment... she's shot down dead. Of course, when OG Gaiden comes out, it turns out to be just a set up for Cliffhanger and she came back... well enough. She's not an Ensemble Dark Horse like Zero, though.
In Persona 3, a large bulk of the games boss fights come from the Full Moon Shadows, extremely powerful Shadows that each represent a different Tarot Arcana. You fight them all...except for Magician, the first to show appear, who is quickly killed by the Main Character in a cutscene.
The first person to die in Catherine is Paul... who is quickly revealed to have been friends since childhood with Vincent and his pals. His death is also treated as a huge shock when it's first brought up, but then quickly forgotten.
The sequel Persona 4 has Saki Konishi, 3rd year student and potential love interest of the Main Character's new buddy Yosuke. She hangs out with them for a bit, gives them info on the first murder, and seems to be set up to be the wise Sempai to the team much like Akihiko and Mitsuru in Persona 3. Then she becomes the 2nd victim of the murder case, there are no upperclassmen to help you out in Persona 4, instead you are the upperclassman and in charge. To make matters worse, when the team finds the place where she died, lingering thoughts of her inner self reveal she always found Yosuke annoying and was only acting nice because he was her bosses' son. Despite knowing that inner thoughts aren't a total representation of the character, due to interaction with his own inner self Yosuke becomes convinced she loathed him for the rest of the game.
Ling in Grand Theft Auto: Chinatown Wars is a very odd case of this, where she is on the cover of the game box, and the poster inside the game is practically a pin-up of her, and then she dies the second mission in.
In The World Ends with You, Rhyme serves this purpose. From up until then, the game was fairly lighthearted, if not slightly confusing. But that one event opens up a whole can of worms and is the final push to set the rest of the plot into motion.
Elia/Aria from Final Fantasy III fits the trope perfectly. She's the first character to appear once you leave the Floating Continent (starting the game properly), gets about half an hour of character development, and is killed by the first boss you encounter.
Wedge and Biggs' death in Final Fantasy VI served to show us how powerful the Espers are.
Wedge and Biggs get offed like this again in Final Fantasy VII, where, after a charming couple of hours of introduction where they're presented as fellow members of the terrorist team, interesting conversation partners and potential future party members, they are killed fighting alongside Barret in an attempt to stop Reno from blowing up the Sector 7 Pillar. A third member of AVALANCHE, Jessie, is the most shocking death of this scene - she isn't doomed to being a Mauve Shirt by her name, gets the most Character Development of the three, and is presented in the opening act as a Rescue Romance love interest to Cloud and a rival to Tifa.
Corporal Richard L. Jenkins in Mass Effect. He has all the potential abilities of a Soldier character, except he's killed by the first enemies in the game in the cut-scene before the fight actually starts. Nihlus, Shepard's appointed mentor, is killed moments later by Saren.
There's also Wilson in the second game - unlike Jenkins, he actually lasts throughout the entire introductory mission working alongside Shepard. Then it turns out he's a traitor and he's shot in the head by Miranda.
Duncan in Dragon Age: Origins dies right right after the Warden's initiation (not to mention that Daveth is killed at the start of the Joining just so Jory loses what little nerve he had and the Warden is the only one who survives).
In Dragon Age: Origins – Awakening, Mhairi is introduced like any companion character would be, with even a little bit more character detail given because you meet her first, but then she dies during the joining.
The sequel features Bethany and Carver, who are inversions of the trope. While one of them always dies depending on your chosen class, the other sticks around as a regular party member... until they, too, either die or are Put on a Bus for some time.
Although Mia Fey of the Ace Attorney series hits all the criteria, the universe itself is not really Anyone Can Die. Even weirder, she sticks around after the fact to serve as the main character's Sexy Mentor through the magic of spirit channelling.
In Heroes of Might and Magic IV, Gauldoth, a Noble Demon necromancer, saves the life of a priest named Alana and brings her with him on a quest so he can have someone to debate philosophy with. She's initially set up as a Morality Pet who believes she can turn Gauldoth to Good, but when Gauldoth realises the dangers involved in activating the MacGuffin, he tricks Alana into activating it instead, killing her.
Fire Emblem: Shadow Dragon (a remake of the original game) adds a new character, Frey, early on that wasn't in the previous versions. It also adds a prologue segment, where, in an object lesson in necessary sacrifice, you have to send one of your units to certain death. Frey has little to no plot relevance and seems to be in the game solely so you can send someone off without losing one of the starting army from the previous versions.
Jesan Nadina in X3: Terran Conflict. He's a mercenary pilot who hired on with a private space force called Operation Final Fury that seeks to drive the Kha'ak completely out of the Community of Planets. He brings the player character into the plot, then has a bridge dropped on him offscreen two missions in.
Just about every grand-strategy level game set in World War II will have entire countries get this treatment just to show how dangerous the Nazis with Gnarly Weapons are. Poland is usually their first and most prominent victim. There is usually no way to save it, and even if the Poles somehow do hold back the Nazis, they'll get attacked from behind by the Soviets. France can also get this treatment, since it will almost invariably be the first major power to fall to the Axis - usually it will not last longer than one year after war is declared.
Fallout 3 has the Lone Wanderer's mother Catherine, who dies in childbirth at the beginning of the game; Jonas, whose death jumpstarts the LW's escape from Vault 101; and later, InitiateReddin, who is crushed by a Super Mutant Behemoth shortly after you first meet the Brotherhood of Steel.
Dangan Ronpa has Sayaka Maizono, the Ultimate Pop Sensation. She's set up to be a Love Interest and is effectively the Deuteragonist of the game until the first chapter, wherein she's the first to die. Another case would be Junko Enoshima, who gets publicly executed by the mastermind in the same chapter for violating a rule. Things are not how they seem in her case, however, as the "Junko" in the game is actually her twin sister Mukuro Ikusaba. The real Junko Enoshima is the one who orchestrated her twin's death, and she's also the mastermind behind the events of the game.