The Storyteller is a descendent of Anya.
At the end of "The True Bride", the Storyteller reveals that after Anya married, they had many children and built a statue of the lion in the garden. The children were told the lion would come to help them if they ever needed it, but the children never quite believed it. A stone lion is shown to be in the Storyteller's house. It opens its blue eyes just as the credits roll.
The Greek Myths series actually happened first.
In the Greek Myth series, the dog seems much more naive and even more physically active. He was originally the Archaeologist's dog, but because dogs age faster than humans, the Archaeologist had to find a new home for his pet since he couldn't keep up anymore. An elderly gentleman who told stories seemed perfect. The dog who lives with the Storyteller is more Genre Savvy
, less active, a tad cynical (no pun intended) and even seems to have a better command of Greek than the Storyteller.
The Storyteller is the Soldier who became immortal.
When he starts his tale he points to the regimental crest on his own jacket to explain that the Soldier belonged to this company. He also has a highly suspect sack (with a strange inhabitant) and very stale biscuits. While he may be an unreliable narrator and just using local props to weave his tale, he could also be telling his own story and it neatly explains the fact that he seems to have been everywhere in europe at one time or another.
Henson blog Tough Pigs makes an interesting case