I feel like you guys are focused more on the story aspect than the actual fight with the boss. The actual fight can entirely make or break the experience.
A boss that is completely fair - all his attacks have power and some scale to them, and all of them can be dodged or disabled with fair warning and moderate skill. But there still is a challenge, and there still must be franticness. A boss fight should be equal parts attacking and defending your health reserves, and either attacking or defending should be done with the player's general skill level.
A boss in FPSs that can attack you like other enemies, but has more health than other enemies, and killing him is just having better conditions and aim than him = bad
A boss in RPGs that is just a pretty powerful guy who you have to outlast = bad
A boss that plomps around and throws rubble, and then completely dies to a few hits in the shin = bad
A boss that stares at you while sending average minions and succumbs pretty easily = bad
And, the great exception to the "Dodging, attacking" rule: bosses that are invulnerable and have stupid attacks that you must dodge, and then stand still and are vulnerable = bad
Really though, I'm taking a more action game look, more like 2D bullethell games and sidescrollers. Contra and Metroid had them, slash and hackers like God of War had them, fast paced games like Quake and Painkiller had them... whatever type of game Metal Gear Solid is has them, the Bouncers in Bioshock,
But for bad boss fights: GLaDOS and Wheatley from Portal (though it is a puzzle game), around every turn-based RPG boss, Fontaine (and everyone but the Big Daddies) from Bioshock, most of Fable's bosses, pretty much all of Arkham Asylum, all of Bethesda's games, Dues Ex, Shadow of the Colossus (but painfully do I say that), Syndicate (2012), and maybe Okami. Those may have been built up bosses, but they weren't epic boss figths - there couldn't have been much tact to fighting them other than shooting a little better or having more health.