The first spiritual leader Goodman Brown sees in the woods is Goodwife Cloyse, an old and pious woman who taught him his catechism along with the minister and deacon of Salem. Brown assumes that she has some godly purpose for being in the woods so late at night, and he wishes to avoid being seen by her. However, when the devil approaches her, she recognizes him immediately and converses with him as a friend. Brown is shocked.
Later, feeling guilty about his reason for being in the woods, Brown hides again when he hears horses coming. Although he cannot see them, he hears the voices of the minister and deacon discussing a meeting with some local "'Indian powows'" who "'know almost as much deviltry as the rest of [the Salemites].'" Brown is shocked, again, to learn that some of the most seemingly righteous religious leaders are, in fact, witches.
It all begins to make more sense when he arrives at the Witches' Sabbath, where he sees that known sinners and people he's always believed to be good and pious folk sit together as equals. Then the Devil himself says that "'Evil is the nature of mankind.'" Thus, no matter who we are -- no matter how seemingly righteous or sinful -- we are all sinners alike: this is our human nature. This explanation, then, accounts for the religious leaders' participation: leaders or no, they are human, and humans are sinners.