It is not true that overall all sequences are equally likely. The probability of a certain sequence is the probability that it would happen by chance added to the probability that it would happen by not-chance. As gjm said in his comment, the chance part is equal, but the non-chance part is not. So there is no reason why the total probability of all sequences would be equal. The total probability of a sequence of 100 heads is higher than most other sequences. For example, there is the non-chance method of just talking about a sequence without actually getting it. We're doing that now, and note that we're talking about the sequence of all heads. That was far more likely given this method of choosing a sequence, then an individual random looking sequence.
(But you are right that it is no more improbable than other sequences. It is less improbable overall, and that is precisely why we start looking for another explanation.)
No, that's a very good reason to start looking for another explanation, but somebody with no understanding of Bayes' Rule at all would do exactly the same thing. If somebody else would engage in exactly the same behavior with a radically different explanation for that behavior, given a particular stimulus - consider the possibility that your explanation for your behavior is not the real reason for your behavior.
Alice: "I just flipped a coin [large number] times. Here's the sequence I got:
(Alice presents her sequence.)
Bob: No, you didn't. The probability of having gotten that particular sequence is 1/2^[large number]. Which is basically impossible. I don't believe you.
Alice: But I had to get some sequence or other. You'd make the same claim regardless of what sequence I showed you.
Bob: True. But am I really supposed to believe you that a 1/2^[large number] event happened, just because you tell me it did, or because you showed me a video of it happening, or even if I watched it happen with my own eyes? My observations are always fallible, and if you make an event improbable enough, why shouldn't I be skeptical even if I think I observed it?
Alice: Someone usually wins the lottery. Should the person who finds out that their ticket had the winning numbers believe the opposite, because winning is so improbable?
Bob: What's the difference between finding out you've won the lottery and finding out that your neighbor is a 500 year old vampire, or that your house is haunted by real ghosts? All of these events are extremely improbable given what we know of the world.
Alice: There's improbable, and then there's impossible. 500 year old vampires and ghosts don't exist.
Bob: As far as you know. And I bet more people claim to have seen ghosts than have won more than 100 million dollars in the lottery.
Alice: I still think there's something wrong with your reasoning here.