Let's divide possible sequences into two broad classes: Distinguished, and undistinguished. Distinguished sequences are those which, for example, are predicted in advance of the coin flips; they have a property which sets them apart from the undistinguished sequences. Undistinguished sequences are all sequences which are isomorphic with respect to the rest of the universe.
All heads is a naturally distinguished sequence; all tails, likewise. Repeating patterns in general. Likewise simple ASCII encodings of binary messages ("This is God, quit flipping that coin").
Once you notice that every sequence can be distinguished somehow (some more readily or naturally than others; for any given input, there's a function that will turn that input into any given output), and that all sequences belong to the "distinguished" set, the odds of getting an interesting-by-some-criteria sequence become 1. Therefore, the mere fact of an interesting quality of a sequence isn't, in itself, interesting, but rather the class of qualities that interesting quality belongs to.
All heads is equivalent to all tails. HTHTHT, repeated as necessary, is equivalent to THTHTH, is lesser interestingness than HHHHHH and TTTTTT. HHTHHTHHT, TTHTTHTTH, HTHHTHHTH, THTTHTTHT, HHHHHHHHH, TTTTTTTTT.
You'll notice that all-heads belongs to multiple sets of interesting qualities; repeated single digit, repeated digit pairs, repeated digit triplets.
There's probably some mathematical language that could be used to describe the "interestingness" of a sequence (I imagine the complexity of the property counts against it?), but I am simply ignorant of it. Depending on the interestingness of the actual sequence Alice shows to Bob, the odds of something of that level of interest occurring should be computable, and may or may not be more likely than some kind of deception or bizarre behavior on the part of the universe.
I think the actual property you're looking for is something like "probability that Alice would produce this sequence by means other than honest coin-flipping accurately reported". All-H is higher probability than something random-looking because there are more-likely scenarios where Alice has a motive for reporting it falsely.
If Alice were a randomly chosen computer program or something, then what you're asking for would be more or less a Solomonoff prior, which is quite popular around these parts, but real-world Alices probably have different patterns of likely deception.
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.