Nowadays, almost every game has at least one boss battle. So here is a dumb question: what types of bosses do you prefer?
You've got the pattern bosses, like the Spider Mastermind and Cyberdemon from Doom 1. These guys move in a fairly predictable pattern, attack in a predictable pattern, and once you know the pattern, you can defeat them.
You've got the puzzle bosses. These guys include Shubb-Niggurath and Cthon from Quake 1, or the creature under the rocket engine in Half-Life, where in order to kill the boss, you need to solve a puzzle. Your weapons have minimal to no effect.
You've got the staged bosses, like the end boss in Beyond Good & Evil or several bosses in the Final Fantasy series. These bosses have multiple forms and personalities, and can be any type of boss.
Finally, there are the "equal" bosses, where you are essentially fighting a clone of yourself and/or your abilities. The Metroid series has been doing a bit of that lately, and games like Quake III: Arena and Unreal Tournament are built around the concept.