This distinction took me a long time to get my head around, too, @nathaniel_hubert. I'm still not 100% I've got things right, but here's how I understand things.
First-distances looks at distances between an individual and the same individual, across changes in state (e.g. time). I suspect initial differences could be a confounding variable in a study, but I don't think pre-existing differences between individuals are the main concern here. Initial state might have an impact on rate of change, but individuals that differ at study outset will still be plotted relative to themselves.
Without a baseline, each distance is presented relative to that individual at the previous state. With a baseline, each distance is presented relative to that individual at some baseline state. Imagine a subject whose microbiome shifts dramatically between week 0 and week 1, and then stabilizes. Without a baseline, rate of change will be peak at the first point, and then drop back with stabilization. If we set week 0 as our baseline, on the other hand, all values after the dramatic change will exhibit a large distance from baseline.
I think this is moving in the right direction! Without baseline, we get a measure of rate of change from each state to the next, which is useful if we're interested in variations in rate of change. Baseline, on the other hand, gives us something concrete to compare against - a pre-intervention state, for example. It's a different viewpoint on the same data.
Anecdotally, I feel like having a baseline often makes the plot simpler to interpret. Clearly, each approach has its use cases, but one feels less complex to me, because each point can be judged relative to a consistent... baseline? Fewer moving parts, I guess. I have a lot more trouble thinking about what rate of change relative to the prior observation means. YMMV.
These methods are discussed in nice clear language in the paper, and come with pretty pictures to boot. Just search for first-distances and you'll find the right sections quickly. If that still doesn't clear things up, let me know and we'll hash it out. 
CK