Bloody Mary is the name of a boss in the 1996 SNES RPG Terranigma, and is perhaps one of the most difficult and scary bosses I have ever encountered in any video game.
Plotwise, Bloody Mary is under the influence of Dark Gaia, the mastermind manipulating forces throughout the game. However, she isn't just evil, she is also insane. She sends her three sons across the Atlantic Ocean with Christopher Columbus, and when they fail to return, locks Columbus in her castle's torture chamber, where the hero of the game, Ark, must rescue him.
Battle with Bloody Mary takes part in three phases: first, you have to move across an empty room to get to a stuffed doll. However, this occurs as a game of red light green light, as you can only move while the doll is talking to you. as you get closer to her, the doll's text scrolls faster, making it harder to move without getting caught. If you move while she is silent, you must start again. Although this sounds like it could be rather tedious, it is actually much more interesting than many "fights" in other games.
After you catch her, you turn to the second phase of the battle with Bloody Mary, where you run around the torture chamber while 4 dolls swirl around you, reciting an eerie poem. Only one of them is real, and you can only attack any of them while you are standing still. If you manage to defeat the doll, you enter battle with Bloody Mary herself.
Bloody Mary is HARD, especially since Terranigma is an action RPG. Unlike Final Fantasy, or other menu based RPG, in which the bosses usually use a devastating magic attack, and the challenge is to find the strategic "soft spot" where the specific magic attack can't hurt you; the challenge to fighting Bloody Mary is to move your character around fast enough to not get hit. This is made doubly challenging by the fact that Mary swoops in a very unpredictable scary pattern, and if she does manage to hit you, it will hurt your character very badly. On the other hand, unless you've spent a lot of time levelling up, your blows will barely hurt her. In all, the entire process of going through her guardians and then fighting Bloody Mary can take half an hour or more, and it maintains tension throughout.
The fight with Bloody Mary is a perfect example of how game designers can integrate plot, atmosphere and the style of attack of an enemy to add not just toughness, but tension.