This depends on several factors, the most important of which would be the pacing of the battle, the circumstances of the battle (both location and story-wise) and the nature of the boss.
For example, a fast-paced platformer or shmup should have a somewhat fast-paced battle theme to go with the gameplay. A turn-based RPG, on the other hand, should focus more on having a theme with an "epic" feel to it.
A creepy and dark boss character needs to have the creepiness reflected in his battle theme. A diabolical entity that puts the viewer in awe, be it through its serenity or its monstrosity, should get an ominous theme.
If the battle seems hopeless or occurs right after (or during) a dramic plot development, this should be reflected somehow. If it is merely the final battle of the supreme forces of light against the supreme forces of evil, it can be triumphant instead. The final battle theme(s) of Seiken Densetsu 3 which Okashii posted are good examples for both.
As you see, context is important. For example, imagine fighting Sephiroth to Native Faith. Imagine fighting Suwako to One Winged Angel. Even though these are both awesome boss themes, when put in the wrong battle they don't seem half as awesome, do they?
In general it is important that the theme is varied enough to not get boring for the duration of the battle, ideally showcasing different aspects of the battle, character or story through different parts.
As was already said, having a song compliment or contrast with the rest of the game can have a powerful effect, too. Compare:
Super Mario 64's final Bowser theme is a very ominous theme for a battle in a comparatively creepy atmosphere whereas the rest of the game had mostly upbeat music, and this change of tone is perfect for delivering the "final battle"-feel.
Banjo Kazooie's final boss theme, on the other hand, is a remix of the "dungeon map" cavern theme which you have heard quite alot during the playthrough of the game, with many different nuances depending on where exactly you were. What's more, the main phrases of this theme appear in
every stage theme in some way or another. The final boss theme takes this familiar tune and arranges it to sound dramatic, frantic and epic during its various parts. Thus it really feels like the battle that concludes everything that came before it.
Similarly, the Champion battle theme from Pokemon Gold/Silver contains parts of the title theme.
As a non-touhou battle theme that scores high in all of the above (but sadly only with the soundeffects of the batle accompanying it), I would like to metnion the final battle theme of
Yoshi's Island. For one who hasn't seen it, the effects of the growth spell come completely out of nowhere, and the ominous music at the beginning of the theme fit perfectly. Then the theme really gets going, and unlike the regular boss theme (which is also good), it is fast-paced
metal. Or at least as much metal as 16 bit can be. :V
Also, the final boss themes by ZUN are obviously awesome in general and especially in fitting with the respective battles. The one that fits the feeling of the actual battle the best is imho Suwa Foughten Field, especially if you time the dialogue so that the opener starts ~ 11.5 seconds into the song. It is not my favorite pice of touhou music, but it accompanies the battle so well, it is glorious...