Meta Ridley from Metroid Prime. Also, the Omega Pirate was a real pain, until I got into the whole swing of fighting him. But Meta Ridley never got easy.
Also, the Core Defender from Command and Conquer: Tiberian Sun - Firestorm was pretty much unkillable by normal means. He came to life and surprised me the first time I played through the game, thusly wiping out my battle weary forces rather quickly. I reloaded and saved right before that point so I could just focus on buidling up an insane amount of forces and then initiating the battle. Still I died. Everytime. Finally, in one my doomed battles with the stupid thing, I had a large division of Hover MLRS set at one portion of the map for reserve that I forgot about. The rest of my forces were destroyed and the Core Defender was headed right for my base, so I ran the MLRS's down to face him (and to most certainly be obliterated). They reached him just as the Defender got through leveling the outer portion of my base and was standing on the bridge in the middle picking off a few guardian infantry. The MLRSs surrounded the bridge while hovering over the water and just let loose on him. To my surprise, the bridge started to crumble and fell apart sinking the Defender like so much scrap metal. I thought myself pretty stupid for not thinking of that earlier.
Also, the DarkSims from Perfect Dark, while not bosses, are harder than almost any AI controlled first person shooter enemy ever.