Bob and Alice are heroes. Bonafide heroes. They beat the bad guys, they save the world, they help old ladies across the street, the whole nine yards.
They also hate each other's guts, perhaps even worse than they do their enemies.
Headbutting Heroes refers to when two heroes thoroughly hate each other, or when one hero hates another hero (it doesn't have to be mutual). This is not the same as the animosity that can form between, say, a Lancer and his superior, since, while they may have animosity against each other, the Lancer deep down respects the Hero and will defer to his leadership. It's also different from Let's You and Him Fight, since the heroes have not been misled to face each other. They really want to duke it out every time they meet, or at the very least they are obviously disagreeable and might try to discredit each other in front of other heroes. They just cannot get along, no matter how others might try to get them to keep it civil.
There need not be actual violence involved in the feud, though. As said before, they might try to discredit each other, or have verbal spats. If there is a threat, they will face that threat, but this will practically never lead to them getting along. In fact, their animosity might even become a hindrance to the situation at hand, and they might get called on it by other heroes sick and tired of their bickering.
The reasons for such animosity are various, but they are rarely very deep. Truly worthwhile reasons for disagreement are also usually reasons they could mediate if they actually sat down and talked it out. However, part of what makes this trope is that the two heroes, deep down, don't NEED an excuse to fight. They just hate each other, and while they might have such a thing as a GOOD reason to fight, it's pretty much secondary to the hatred that has formed between them. Their reasons for disagreement could disappear, they could both grow more mature and understanding, and they'd STILL hate each other.
Examples of reasons for these characters hatred for each other might include:
Racism: While this may seem like a reason that makes either or both of the heroes seem VERY non-heroic, it might also be a reason so ingrained in them from their upbringing that it's actually kind of tragic. For example, a Kree hero and a Skrull hero might be two guys who are admired and respected by the hero community at large, but they will NEVER get along because their cultures practically revolve around hating the other one's race.
Never Living It Down: One of the heroes did something in the past or failed in some way that has tainted them in the eyes of others, but while most heroes give him the benefit of the doubt or believe the hero has proven his worth, the rival just won't let it go.
Pride: The heroes see each other as a rival to be bested, and any action by the other hero is seen as a challenge or insult. Definitely the most petty reason AND the most permanent one. With any other reason, it might be marginally justifiable for there to be a rivalry between the heroes.
Quite obviously, Anti Heroes are VERY prone to this type of relationship with full-fledged heroes. It's almost a prerequisite of being an anti-hero that a full-fledged hero will hate your guts. Sociopathic heroes are also prone to this, for obvious reasons.
Subtrope of Divided We Fall that involves individuals rather than factions. Compare to Teeth-Clenched Teamwork, where, while hating each other, the heroes are willing to set aside their difference for the sake of doing what's right. Fighting The Lancer is when the teammates can't set aside their differences, and comes to blows. Compare Dueling Messiahs where it's both heroes who are like with each other due to their conflicting methods to save the world. See also No Sympathy Between Mooks which is the villainous version.
Probably Un-Go's Shinjuro Yuki and Kaishou Rinroku qualify as this, although we don't actually know how much Kaishou hates Sinjuro, and they both act civilized about this and usually even cooperate. Clashing ideologies are at fault in this case.
Kazuma and Ryuho of Scryed may have common goals at times, but once they're taken care of, it's back to fighting each other. Their ideologies and personalities, and their stubborn pride, make for unresolvable differences. The very last episode is a knock-down, drag-out fight between the two of them, with no hint of friendship apparent between the two.
In the Mai-Hime manga, Nao doesn't get along well with any of the other Himes, especially not Natsuki and Haruka. Unlike in the anime, however, she never turns completely hostile against the others after joining them.
Batman has a tendency to rub many other heroes the wrong way, with some of them actually going hostile on him. Superman is not one of them (which can surprise people, considering how opposite they are portrayed usually), but Hal Jordan and especially Guy Gardner are. Harvey Bullock is sometimes portrayed this way towards him too, but he eventually gets better.
The way Frank Miller, and then John Byrne, conceived the Batman/Superman relationship played this trope straight, with Frank Miller noting that their ideologies are completely different and concluding that 'These two people do NOT like each other'.
The Hulk REALLY has this in spades. He has loads of characters he'll never get along with. Amongst them, Thor is the one with whom he has the biggest rivalry. The Juggernaut, Wolverine and Ben Grimm are also common rivals.
As far as the Hulk goes, he and Thor will occasionally get along perfectly well until one sets the other off, and a fight breaks out. Hulk and Ben also have mutual respect for each other. That being said, the Hulk does have a few heroes he absolutely hates, especially after the Planet Hulk / World War Hulk incidents. Reed Richards, Tony Stark, and Professor X being among them. Wolverine and Juggernaut, on the other hand, are purely antagonistic with the Hulk.
Wolverine can't go a week without running into a hero who wants to beat him up. If said hero is a government agent or came from the Weapon X program, even more so.
The Punisher is a surprisingly dark anti-hero. He kills frequently in ways which are Bloody Hilarious, simply brutal, or just Gorn. Additionally, he readily goes all-out with firearms. As the name implies, mercy is not one of his virtues at all. This doesn't help his popularity with more idealistic heroes. Since he was first introduced as an adversary of Spider-Man, it's not surprising that Webhead isn't a fan.
Rorschach is considered a lunatic and subversive by the authorities, and most heroes don't want anything to do with him. Laurie Juspeczyk, specifically, can't stand him at all.
Ms. Marvel carried a grudge against Rogue for quite a while for Mind Raping her to steal her powers back when Rogue was still a villain working for Mystique. They eventually reconciled (but whether any given writer remembers that is up for grabs).
Dungeon Keeper Ami features this with a very interesting twist. Sailor Mercury is a unquestionably heroic character displaced by interdimensional weirdness, and, through no fault of her own, has been made a Keeper. Keepers usually have a dash of The Unfettered thrown in. The worst count as OmnicidalManiacs. Mercury is nothing like this. The Light's forces, however, are extreamely reluctant to consider her as anything but a madwoman to be eliminated. The Avatar outright states that he has difficulty tolerateing her on an emotional level, due to the crimes perpetrated against his people by Keepers, and he's one of the more open-minded of the Lightworld rulers.
Film - Live Action
Happens in The Avengers, and many have argued that this is part of the movie's appeal: successfully translating the complex dynamics of the heroes' relationships in the comic books to the big screen. It is a very large plot point actually.
This sums up Tal and Millas relationship from book 1-4 of The Seventh Tower pretty nicely, and in five, there is a certain frostiness to their relationship. Most of it comes from Millas pig-headed aggression towards Tal, who is someone she disliked from the moment she saw him and never quite let go of it, but Tals condescending attitudes towards anyone who isn't a Chosen certainly don't help matters. Milla would have killed Tal if she'd had the chance. Tal simply wants rid of her. Nonetheless, they put their differences aside to fight the greater evil and accomplish their objectives, and while you could put that down to simple necessity, both Tal and Milla put their own lives in danger to save the other when necessary.
Tash and Maga, in Galaxy of Fear. Maga sees Tash's Force powers as taking attention from him, his tribe's garoo or shaman/leader. Tash thinks he hates her, and later has to confront her own racism towards someone whose people still wear skins and live as nomads.
Frank Pembleton in Homicide: Life on the Street is much like the Batman example. While Pembleton is an extremely talented detective, dedicated to his job and willing to see all murder victims as equals, he generally rubs those in his squad the wrong way, considering them amateurish by comparison. Having said that, his squad members get along with him considerably better than other members of the police force.
Sherlock Holmes in Sherlock and most of Scotland Yard.
John Cena and The Rock are both supposed to be "heroes" (i.e., babyfaces— Cena gets booed more than almost any other face ever, though), and they can't stand each other at all. Same applied to Shawn Michaels and The Undertaker towards the end of the former's career, although that was more due to Michaels' (kayfabe) obsession with defeating Undertaker at WrestleMania.
In Dragon Age II, this is very prevalent when it comes to both Fenris and Anders, both of whom have very strong opinions when it comes to the Mage/Templar conflict of the game. Fenris has a deep distrust of mages due to growing up as a slave in the Tevinter Imperium, an Always Chaotic EvilMagocracy, while Anders is an advocate of mage rights possessed by a spirit incapable of seeing shades of gray (to the extent that the spirit's influence eventually drives Anders to extremism). Unsurprisingly, the two despise each other - though Anders eventually becomes such an extremist that he sees nearly anyone as a potential enemy. Still, if there's one thing that the two agree on, it's that both of them dislike Merrill for being a Blood Mage (a very taboo and controversial form of magic in the setting).
It's not just in Dragon Age II. In the first game, Alistair and Morrigan hate each other from the first words they exchange and continue to exchange bile-filled insults throughout the entire game, right up until the end.
Detective Cole Phelps and DA Investigator Jack Kelso in L.A. Noire.
Most of the party in Star Wars: Knights of the Old Republic II harbors some kind of deep-seated dislike for at least one other crewmate. Bao-Dur can't stand Mandalore, Atton can't stand the Disciple, Brianna won't trust Visas, T3-M4 and HK-47 have a conversation that ends with a tazing, and nobody likes Kreia except the Exile herself.
Throughout the many The Land Before Time films, Littlefoot and Cera avert this in the usual sense (except in the first movie, where it's played straight), but the trope holds true in the literal sense: at several points they've actually butted heads.