This is probably just because the coins aren’t actually fair. If the coin is slightly biased towards heads, the first throw is more likely to heads, and so are all subsequent throws. Same for tails.
That's not the problem. You can test that by using a highly secure random number generator, e.g. /dev/random in Linux, to select the initial side. Keep track of that initial side, record the side it lands on. This paper shows a same-side bias, not a heads bias.
That's the opposite of what the paper says. If the coin was biased you'd expect it to land on heads more often regardless of what side it starts on. The coins land on the side they start on more often.