Straightforward solution, due to eisirrational: Let $a_i = s_{i+1}-s_i$ and let the (minimal) period of $a_i$ be $m$. We shall show that $m=1$, which means that $s_i$ is an arithmetic progression and all values of $N$ are precisely values satisfying $k^2 \leqslant N < k^2+k$ for some positive integer $k$. Let $s_m-s_0 = t$. Notice that $s_{i+m}-s_i = \sum_{j=i}^{i+m-1} a_j = \sum_{j=0}^{m-1} a_j = t$, meaning that this difference is constant across all $i$. It also follows that for any number $k$, if $m\mid i-j$, then $s_{i+k}-s_i = s_{j+k}-s_j$, so the difference of two terms of the sequence that are $k$ apart is constant as the indices of these terms is fixed modulo $m$. Let $d = \gcd(m, t)$. The key idea is to consider minimizing the value of $s_{s_{n+1}+1}-s_{s_n}$ (as this minimum value must be greater than $s_{s_{i+1}}-s_{s_i}$ for all $i$). In this expression, if $n$ increments by multiples of $m$, then the indices $s_{n+1}+1$ and $s_n$ increment by multiples of $t$, so their difference is constant (namely $a_n+1$), and furthermore, $s_n$ and $s_{n+1}+1$ each achieves, modulo $m$, precisely all numbers in an arithmetic sequence of common difference $d$. It then follows that he minimum value can achieve the minimum value of $s_{x+a_n+1}-s_x$ over $x$ congruent to $s_n$ modulo $d$. More formally, Claim: If $d\mid s_i - s_j$, then $a_i=a_j$. Proof: Assume otherwise, and without loss of generality that $a_i>a_j$. Let $x$ be a number such that $x\equiv s_j \mod d$ and for all $y\equiv s_j \mod d$, $s_{y+a_j+1}-s_y \geqslant s_{x+a_j+1}-s_x$. By Bezout's, there exists a positive integer $k$ such that $s_{j+km} = s_j+kt \equiv x \mod m$. We thus have that $$s_{s_{j+1+km}+1} - s_{s_{j+km}} = s_{s_{j+km}+a_j+1} - s_{s_{j+km}} = s_{x+a_j+1}-s_x \leqslant s_{s_i+a_j+1} - s_{s_i} \leqslant s_{s_{i+1}}-s_{s_i}$$which is a contradiction. $\square$ By Pigeonhole, there exists $i, j \in {0, 1, \ldots, d}$ with $i>j$ such that $d\mid s_i-s_j$. The claim implies that whenever $d\mid s_i-s_j$, we have that $d\mid s_{i+1}-s_{j+1}$, and inductively, $d\mid s_{i+k}-s_{j+k}$ for all positive integers $k$. Hence, the sequence $s_j, s_{j+1}, s_{j+2}, \ldots$ is periodic modulo $d$ with a period of $i-j$. The claim now implies that $a_j, a_{j+1}, a_{j+2}, \ldots$ is periodic with a period of $i-j$. Yet, $m$ is the minimal period of $a_1, a_2, \ldots$, so consequently, $m\mid i-j$. As $i-j \leqslant d$, it follows that $m=d$ and $i=d$, $j=0$. In particular, this means that the sequence $s$ is periodic modulo $m$ with period $m$, and $s_0, s_1, \ldots, s_{m-1}$ are distinct modulo $m$. To finish, let $a_n$ be the maximal element of the $a$ sequence, and let $s_{n+1} \equiv c \mod m$. Now, let $n_1$ be a positive integer such that $s_{n_1+1} \equiv c-1 \mod m$ (which we know exists since the sequence $s$ is surjective and periodic modulo $m$). If it were the case that $a_{n_1}<a_n$, we would have $$s_{s_{n+1}}-s_{s_n} < s_{s_{n_1+1}+1}-s_{s_{n_1}} = s_{s_{n+1}} - s_{s_{n_1}+s_{n+1}-s_{n_1+1}-1} \leqslant s_{s_{n+1}}-s_{s_n}$$which cannot hold. Thus we have that $a_{n_1}=a_n$. By constructing a sequence $n_2, \ldots, n_{m-1}$ satisfying $s_{n_i+1} \equiv c-i \mod m$ and repeating the above argument, we see that $a_{n}=a_{n_1}=\ldots = a_{n_{m-1}}$. Clearly, $n, n_1, \ldots, n_{m-1}$ are distinct modulo $m$, so the sequence $a$ must be constant, as desired. Day 1 of TSTST should have been reversed - #3 as #1, #2 as #2, and #1 as #3.

Solution. the only $N$ that works is between $t^2$ and $t^2+t-1$ for some $t$ inclusive. The construction is $f(x)\equiv tx$ Suppose $f(x+D)=f(x)+E$ for all $x\in \mathbb{N}$, where $D$ is the minimal period of $f(x)-f(x-1)$ Claim: $f(1), \cdots, f(D)$ is injective mod $D$. Proof: suppose $f(a)\equiv f(b) (\bmod\; D)$, then $$f(1+f(a+1))-f(f(a))>N\ge f(f(a+1))-f(f(a))$$ $$f(1+f(b+1))-f(f(b))>N\ge f(f(b+1))-f(f(b))$$ I claim $f(a+1)-f(a)=f(b+1)-f(b)$. Let $f(a)=f(b)+Dk$. If $A=f(a+1)-f(a)>f(b+1)-f(b)=B$ then $$N\ge f(f(a+1))-f(f(a))=f(f(b)+A+Dk)-f(f(b)+Dk)=f(f(b)+A)-f(f(b))\ge f(f(b)+B+1)-f(f(b))$$ $$=f(f(b+1)+1)-f(f(b))>N$$ Absurd Hence $f(a+1)\equiv f(b+1) (\bmod\; D)$. Continuing in this manner, we can see $g$ has period $\gcd(D,b-a)$. Therefore, $D|E$ and let $E=kD$ Now we can see that $\mathbb{E}[f(f(n))-f(f(n-1))]=k^2$ and $\mathbb{E}[f(f(n)+1)-f(f(n-1))]=k^2+k$ as $f(1),\cdots,f(D)$ is a bijection mod $D$. Since $$k^2=\mathbb{E}[f(f(n))-f(f(n-1))]\le N<\mathbb{E}[f(f(n)+1)-f(f(n-1))]=k^2+k$$the conclusion follows.

As promised, here is the full solution. It is due to eisirrational, and I shall present it with some intuitive explanations:

Here is how I motivated my solution: SPOILER ALERT

Let's see how fast I can write this up. Clearly we care only about $d_i = s_{i+1} - s_i$ which we are given is periodic. Suppose it has minimal period $m$. We claim that that for any admissible value of $N$, the associated sequence $d_i$ has period $1$ in which case the solution set mentioned in the above solutions follows. So suppose $m \neq 1$. We show that there exists integers $p$, $q$, and $k$ so that: $$s_{q-1} \leq s_{p-1} + km < s_p + km \leq s_q - 1 \qquad (\ast)$$This is sufficient because it follows that: $$s_{s_p + 1} - s_{s_{p-1}} = \sum_{i=s_{p-1}}^{s_p} d_i = \sum_{i=s_{p-1}+km}^{s_p+km} d_i \leq \sum_{i=s_{q-1}}^{s_q - 1} d_i = s_{s_q} - s_{s_{q-1}}$$In which case clearly no $N$ exists simultaneously being less than the LHS and greater than the RHS. So suppose the contrary. Note that $s_i \bmod m$ fixes $s_{i+1} \bmod m$, else we have $i$ and $j$ so that WLOG, $d_i > d_j$ and we can get $s_i = s_j + km$ and $$s_{j+1} + km = s_j + km + d_j \leq s_i + d_i - 1 = s_{i+1} - 1$$so $(\ast)$ is satisfied. We now claim that there exists that for every $a$, there exists $i$ such that $s_i \equiv a \bmod m$ OR exist $i, j$ such that $d_i - d_j \geq m$. This is true since the previous fact gaurantees that $s_i \bmod m$ cycles among the range of residues, so either $d_i$ itself cycles similarly or there exists some $i$ and $j$ such that $d_i - d_j$ is a positive multiple of $m$. In the latter case we are finished with the claim, if the former then given that the minimal cycle of length is $m$, it must cycle through all possible residues. In the case where we are given $d_i - d_j \geq m$, we immediately have the contradiction we wanted since there always exists $k$ such $s_{i-1} \leq s_{j-1} + km < s_j + km \leq s_i - 1$. In the other case where or every $a$, there exists $i$ such that $s_i \equiv a \bmod m$, pick $i$ so that $d_i$ is maximal. If we pick $j$ so that $s_j \equiv s_i + 1 \bmod m$, then we can pick $k$ so that $s_j + km = s_i + 1$. Now $(\ast)$ will be easily satisfied unless $d_j \geq d_i - 1$. If equality holds then this breaks the cycle nature. So actually $d_j \geq d_i$, and because $d_i$ maximal, in fact $d_j = d_i$. Now this can be inductively extended by incrementing $s_k \bmod m$ to show that in fact all $d_i$ are actually maximal. But then the period must be $1$, our last contradiction needed. $\square$

The answer is $N=k^2+a$ for integers $k,a$ satisfying $0\leq a \leq k-1$. This can be obtained by $s_n\equiv kn$. We now prove no other $N$ are possible. Let $d_i=s_{i+1}-s_i$, let it have minimal period $p$. If $N$ exists, then for any positive integers $x,y$ we have: $$s_{s_x} - s_{s_{x-1}} \leq N < s_{1+s_y} - s_{s_{y-1}}\quad (\textasteriskcentered)$$ Claim: If $s_i\equiv s_j\pmod p$ then $d_i=d_j$ and in particular, $i\equiv j\pmod p$. Proof: Assume the contrary. Then assume WLOG $d_i+1\leq d_j$, so by $(\textasteriskcentered)$: $$s_{s_j+d_j} - s_{s_j} = s_{s_{j+1}} - s_{s_j} < s_{s_{i+1}+1} - s_{s_i} = s_{s_i+d_i+1} - s_{s_i} = s_{s_j+d_i+1}-s_{s_j}\leq s_{s_j+d_j}-s_{s_j}$$a contradiction, so $d_i=d_j$. Assume FTSOC that $i\not\equiv j\pmod{p}$ and WLOG assume $1\leq i, j\leq p$. Reiterating with $s_{i+1}\equiv s_i + d_i\equiv s_j + d_j\equiv s_{j+1}\pmod p$ yields that $d_1, d_2,\ldots$ has period $0<\lvert i-j\rvert<p$, contradicting $p$'s minimality. Now $\{s_1,s_2,\ldots, s_p\}$ form a complete residue set $\pmod p$. We will show that $d_i$ is in fact constant. Let $f(n)$ be the unique integer satisfying $1\leq f(n)\leq p$ and $s_{f(n)}+1\equiv s_n\pmod p$. Then $\{n, f(n), f(f(n)), \ldots, f^{p-1}(n)\}$ is also a complete residue modulo $p$ because if $f^i(n)\equiv f^j(n)\pmod p$ for $0\leq i, j \leq p-1$ then $$s_{f^i(n)}\equiv s_{f^j(n)} \equiv s_{f^i(n)} + j-i\pmod p$$giving $i=j$. Choose $t$ such that $d_t=\alpha$ attains the maximal value across all $1\leq t\leq p$. Inductively, we will prove that $d_{f^k(t)}=\alpha$ for all $0\leq k\leq p-1$. The base case is true; for the inductive way, assume FTSOC that $d_{f^m(t)}\leq \alpha -1 = d_{f^{m-1}(t)-1} - 1$. Then by $(\textasteriskcentered)$ substituting $x=f^{m-1}(t)$ and $y=f^m(t)$ we have: $$s_{s_{f^{m-1}(t)}} - s_{s_{f^{m-1}(t)-1}}< s_{s_{f^m(t)}+1} - s_{s_{f^m(t)-1}} = s_{s_{f^{m-1}(t)}} - s_{s_{f^m(t)-1} + s_{f^{m-1}(t)} - s_{f^m(t)} - 1} \leq s_{s_{f^{m-1}(t)}} - s_{s_{f^{m-1}(t)-1}}$$where the last inequality follows from $s_{f^{m-1}(t)} - s_{f^{m-1}(t)-1} \geq s_{f^m(t)} - s_{f^m(t)-1}$, giving a contradiction. Thus, $d_{f^k(t)}=\alpha$ for all $0\leq k\leq p-1$ so $d_i$ is constant. Thus, $s_n=\alpha n+c$ for all $n$: $$[\alpha(\alpha n + c) + c] - [\alpha(\alpha (n-1) + c)+c]\leq N < [\alpha(\alpha n + c+1) + c] - [\alpha(\alpha (n-1) + c)+c]$$giving $$\alpha^2 \leq N < \alpha^2 + \alpha$$as needed.

The answer is all $N$ satisfying $k^2 \leq N<k^2+k$ for some positive integer $k$, which are precisely the $N$ achieved with arithmetic sequences. I will show that, in fact, the only sequences where $\max\{s_{s_i}-s_{s_{i-1}}\}_i<\min\{s_{1+s_i}-s_{s_{i-1}}\}_i$, i.e. the only sequences where some $N$ exists, are arithmetic sequences, which finishes the problem. Let $a_i=s_{i+1}-s_i$ and let $d>1$ be the minimal period of $a_i$. For any fixed $i$, the sequence $s_i,s_{i+d},s_{i+2d},\ldots$ hits some modulo-$d$ residues forming an arithmetic progression with difference $\gcd(d,s_{i+d}-s_i)$. Claim: If $s_i \equiv s_j \pmod{d}$, then $a_i=a_j$. Proof: We should have $$s_{s_{i+1}}-s_{s_i}<s_{s_{j+1}+1}-s_{s_j} \implies s_{s_i+a_i}-s_{s_i}<s_{s_j+a_j+1}-s_{s_j} \implies a_i<a_j+1,$$using the periodicity fact. Likewise, $a_j<a_i+1$, so $a_i=a_j$ follows. $\blacksquare$ Using the above claim, it follows that $s_i \equiv s_j \pmod{d} \implies s_{i+1} \equiv s_{j+1} \pmod{d}$. Applying this repeatedly implies that the $a_i$ are have period (not necessarily minimal) $|i-j|$. Thus by definition, $s_i \equiv s_j \pmod{d} \implies i \equiv j \pmod{d}$. Then, by Pigeonhole each sequence $s_i,s_{i+d},\ldots$ occupy exactly one modulo-$d$ residue that uniquely corresponds to $i$ modulo $d$. Therefore, $r \in \{0,\ldots,d-1\}$, let $k_r \in \{0,\ldots,d-1\}$ be unique such that $s_{k_r} \equiv r \pmod{d}$; note that the $k_r$ are pairwise disjoint. Select $r$ such that $a_{k_r}$ is maximal; I claim that $a_{k_{r+1}}=a_{k_r}$. We should have $$s_{s_{k_r+1}}-s_{s_{k_r}}<s_{s_{k_{r+1}+1}+1}-s_{s_{k_{r+1}}} \implies s_{r+a_{k_r}}-s_r<s_{r+a_{k_{r+1}}+2}-s_{r+1}.$$If $a_{k_{r+1}} \leq a_{k_r}-2$, we obtain an immediate contradiction since $s_{r+a_{k_r}} \geq s_{r+a_{k_{r+1}}+2}$ and $s_r \leq s_{r+1}$. If $a_{k_{r+1}}=a_{k_r}-1$, then $$s_{k_{r+1}+1} \equiv s_{k_{r+1}}+a_{k_{r+1}} \equiv r+1+a_{k_{r+1}} \equiv r+a_{k_r} \equiv s_{k_r+1} \pmod{d},$$so $k_{r+1}\equiv k_r \pmod{d}$: absurd. Hence by maximality $a_{k_{r+1}}=a_{k_r}$, and repeating this implies $a_i$ is constant, or $d=1$: contradiction. $\blacksquare$