Gimmicks. I cannot say this enough.
If your boss is in the typical RPG interface, put in a few spiffy effects, talking heads, cool looking graphics, status effects, and doom. Lots and lots of doom! Plus, if it's the final boss, pulling a surprise final boss after the boss everyone thought was a final boss can work (although that's somewhat cliche by now.)
If you do it on ABS, like I do, the best boss battles are the one where you don't just walk up to the boss and slam it. Give it attacks with funky range that you have to dodge, make the players have to solve a sort of puzzle to get to it, etc etc.
In any category, bosses should always be unique; a boss that just looks like a very big normal enemy gets old fast. (That niche is more for minibosses.) Plus, a boss that gives the player a good laugh can be good for comic relief once in a while (this category includes bosses that are stronger than they look, bosses that are a lot weaker than they look, and bosses that are just plain ridiculous.)