Using Markov chain theory, it is not hard to show that the expected time until the process hits state "1" starting at $N_0$ is $1+1+1/2+\cdots+1/(N_0-1)$.
Correction
In my previous answer, I mistakenly chose a new state uniformly from $[1,\dots, N_i]$ instead of $[1,\dots, N_{i-1}]$. The expected hitting time of state "1" for the OP's model starting at $N_0$ is $1+1/2+\cdots+1/(N_0-1)$. This is one less than my first answer.
