The one boss that immediately jumps out at me was the fortress boss in Aerofighters Assault on the N64. That thing was beastly. After weeks I finally developed a strategy for beating it, but it was slow, painstaking, and not always successful (it involved much kamikaze...).
Some of the bosses in Zelda II on the NES were pretty hard, too.