Definitely 'have'. At least in BrE. It's the only possibility, because only the dogs have tails.* Even omitting the dogs, you say that the majority have long tails. It's a quantifying word like 'lot', 'number', whose number is always ignored: Some dogs have short tails, but a lot have long tails.
* That makes it different from some other group words: if a group of dogs is/are attacking me, then it's true both that the dogs are attacking me and that the group is attacking me. A group can attack, but a majority can't have a tail.