The behaviour of <Range<_> as Iterator>::nth has a slight mismatch with StepBy (or Step depending on your viewpoint) as @scottmcm has found out, resulting in sub-optimal performance.
On every iteration, the range has to first step forwards n-1 times to get the next element and then advance again by 1.

I'm hoping we can improve step_by into a 100% zero-cost abstraction.

It seems like the performance issue is specific to StepBy<Range>. I'm thinking therefore that we could specialize Iterator for StepBy<Range<I>> such that it would use @scottmcm's suggested semantics. Like this:

impl<I> Iterator for StepBy<Range<I>>
where
    I: Step
{
    fn next(&mut self) -> Option<Self::Item> {
        self.first = false;
        if let Some(mut n) = self.start.add_usize(self.step+1) {
            if n < self.end {
                std::mem::swap(&mut self.start, &mut n);
                return Some(n);
            }
        }

        self.start = self.end.clone();
        None
    }
}

That also avoids the branch on a regular next(). I haven't looked at the other methods but that boolean in StepBy could possibly become superfluous. During construction of the StepBy adapter, the size in .step_by(size) is decremented and this specialization has to counter-add 1 every time but that should be optimized away if inlined.

If someone were to depend on side-effects in Step::add_usize (when the trait is stabilized), this pre-stepping would become weird. Same thing with a hypothetical next_and_skip_ahead().

@scottmcm what do you think of this?