I can't really remember much in the way of tough boss fights, but ye gahds, the aforementioned underwater boss in Bomberman Hero fight really put me off. I think I only managed to beat it because I Gamesharked myself up a bunch of extra hitpoints (yeah, I bought a Gameshark even though the European equivalent is the Pro Action Gameplay. I think it only worked on my two Bomberman games. Amusing anecdote!).
Some of the bosses I fought in Twilight Princess before giving up on the game weren't exactly difficult, but did tend to have some really moronic obstacles. The giant multi-headed plant thing (Baba?) in one of the early dungeons (if not the first one), I could lock onto it and whirl those bombs at it, but they would just never hit. It wasn't attacking me, and I was incapable of hitting it, so I was fiddling around for about twenty minutes before I realised the bomb only hits if you don't lock onto the plant. Urgh.