The difference between these two words is subtle: Should: this indicates when something might happen, but not for sure. For instance, in your sentence,” where should we go next,” should indicates that the person is asking where to go next, but it’s not guaranteed they will go there. So, more of asking for suggestions than anything. Shall: this indicates when something will happen without a doubt. For instance, in your sentence,” where shall we go next” means that for sure they will go somewhere. Please note, from my experience in USA English, I have heard “should” and “shall” used interchangeably by people when they are asking questions similar to the sentences you posted, but there is a difference.

"Should" tells you what you have to do and it would be better for you. In the first quastion you are asking: Where should we go (to do something better or to cross a trace faster etc.). In other words you are asking for advise. In the second quastion you are simply asking where you are supposed to go. But it is not necessarily better way. You could just say: "Where are we going next time?" Asking the other person where he or she wanna go or where a third person want you to go. Anyway these two words are similar but "shall" is used rather in quastions.