Mostly agree with Lacrymas, but I think you're missing a key component. They should be fun!
My first sentence was that they can be memorable and fun :p I mostly concentrated on the mechanical aspects and neglected the aesthetic and creative ones. Of course they should be fun and creative, with interesting mechanics and cool visuals and all that jazz :p There is another type of boss battle that I neglected as well, because of being too focused on the mechanics. Dialogue fights. Think Planescape Torment. There was a way to fail conversations in that game if you didn't pay attention and there was a way to talk yourself out of some bosses. Even the final boss. This is the hardest thing to do because it relies very heavily on good writing and all concepts that entails.
