The first thing that came to mind on loyalty as a bad thing, is remember that loyalty to a person means serving their interests as you see them. This leads to a rich area for conflicts without treachery. A loyal character may hold back information to spare the protagonist from knowing it. Or they may do things that serve the protagonist's ends by means the protagonist would condemn. Or they may try to stop the protagonist from enacting their latest heroic plan/harebrained scheme. A person being loyal to the protagonist doesn't translate into doing what the protagonist wants. If it always does, it destroys characterization.
A great example of that shows up in the webcomic Looking For Group. The elven protagonist, Cale, is gathering a disparate bunch of people into an army to rebuild an ancient city. At one point he meets a bunch of gnomes who are being swarmed by an overwhelming enemy force, and tries to convince them to retreat, but they're still not certain that they're beaten and they want to keep fighting. Cale and his group know full well that in a few months the gnomes will retreat anyway, and without Cale's team supporting them, they'll get slaughtered. So this one dwarf quietly sneaks into the gnome's camp and kills several of their guards, allowing the enemy to swarm them and forcing them to retreat with Cale. When Cale realizes this, he is furious at the dwarf for killing 'good guys', even though he understands her reasons.