Fatalities
Fatalities are special animations played at the end of a match. When the opponent's life is reduced to zero in the final round, they will be stunned and the message "Finish Him/Her" will appear. At this point you may hit the opponent with any move to end the match and play the standard victory animation. You may also enter a command specific to your character to trigger a Fatality animation. You may also do nothing at all, in which case the opponent eventually just falls over anyway. Each character has two Fatalities.
You can perform an Easy Fatality by pressing BL+Hold 1 or BL+Hold 2 at the end of a match. This performs a Fatality in the standard way but costs an Easy Fatality Token, which are obtained from graves in the Krypt or by buying them as DLC. Performing Fatalities counts towards challenges and may grant XP and Koins but has no benefit in the fight itself.
Faction Kills
Faction Kills resemble Fatalities except the options you have access to are determined by your Faction and Faction Level rather than your choice of character. Faction Kills are performed in exactly the same way as Fatalities except with different motions. There is no "easy" option for Faction Kills.
Brutalities
Brutalities are special animations associated with regular Special Moves that are used if the Special Move reduces the opponent to zero in the final round. Unlike Fatalities, Brutalities are performed during the fight, not at the "Finish Him" screen. To perform a Brutality you must at least end the last round with a particular special move; depending on your character and the specific Brutality you may also need to modify the motion of that special move, or meet other conditions during the fight. Each character has 5 Brutalities, but initially only one is unlocked; the remainder must be unlocked in the Krypt. If a Brutality is successfully performed, the "Finish Him" screen is skipped and a different victory animation is played.
As with Fatalities, performing Brutalities counts towards challenges and may grant XP and Koins but has no benefit in the fight itself.