Answer to question 1
There are many ways the first quantum algorithm for order finding could have been conceived and I don't know how it really happened. However, here is a plausible though entirely fictional account of how one might have arrived at it:
Alice: Hey, I was imagining doing arithmetic on a quantum computer and made a unitary that computes multiplication modulo a given integer $N$.
Bob: Hey, that's cool! What is it?
Alice: Well, it really just permutes the computational basis states like this
$$
U|y\rangle = |xy\pmod N\rangle\tag1
$$
when $x$ and $y$ are coprime to $N$ and acts as identity otherwise.
Bob: Right. I wonder what $U$'s eigenvalues are...
See the answer to question 2 below for details of what occurs here. Some time later:
Alice: So the eigenvalues are $\exp\frac{2\pi i s}{r}$ for $s=0,\dots,r-1$ where $r$ is the order of $x$ modulo $N$.
Bob: Interesting... Wait, what?!... We can use the Quantum Phase Estimation algorithm to compute eigenvalues of any unitary. This means we could use QPE to find $r$!
Alice: You're right! Wasn't finding $r$ supposed to be computationally hard?
Bob: On a classical computer? As far as we know, yeah.
Alice: Looks like it's computationally easy on a quantum computer!
Answer to question 2
As in question 1, there are many ways one can arrive at the result. The following elementary approach is loosely inspired by the power iteration algorithm for finding eigenvectors and eigenvalues. Note that if $|v\rangle$ is an eigenvector of $U$ associated with eigenvalue $\lambda$ then
$$
U^k|v\rangle = \lambda^k|v\rangle.
$$
However, from the definition of $U$ in $(1)$ we know that
$$
U^k|y\rangle = |x^k y\pmod N\rangle
$$
for a computational basis state $|y\rangle$ encoding a $y$ coprime to $N$. Now, let $r$ be the order of $x$ modulo $N$, i.e. $x^r = 1\pmod N$. Then,
$$
\lambda^r|v\rangle = U^r|v\rangle = |v\rangle
$$
and we see that $\lambda$ is a number such that
$$
\lambda^r = 1.
$$
In other words, the eigenvalues are the $r$th roots of unity
$$
\lambda = \exp\frac{2\pi i s}{r}\tag2
$$
for $s = 0,\dots,r-1$.
Having found the eigenvalues, we now want to find the corresponding eigenvectors. We begin with the observation that $U$ permutes the states $|x^0\pmod N\rangle,\dots|x^{r-1}\pmod N\rangle$. Consequently, the uniform superposition
$$
|v_0\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}|x^k\pmod N\rangle\tag3
$$
is an eigenvector associated with eigenvalue $1$. Hoping that $(3)$ might be a special case of a more general pattern, we next try
$$
|v_{a_0,\dots,a_{r-1}}\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a_k|x^k\pmod N\rangle\tag4
$$
for some complex numbers $a_0,\dots,a_{r-1}$. If we apply $U$ to both sides of $(4)$, we get
$$
U|v_{a_0,\dots,a_{r-1}}\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a_k|x^{k+1}\pmod N\rangle
$$
which shifts the kets by one position cyclically relative to the coefficients $a_k$. However, by definition of eigenvector, we need this reshuffling to allow us to pull a constant out in front of the sum, so we see that we need $a_k = a^k$ for some constant $a$, i.e.
$$
|v_a\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^k|x^k\pmod N\rangle.
$$
Let us try it
$$
\begin{align}
U|v_a\rangle &= \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^k|x^{k+1}\pmod N\rangle \\
&= a^{-1}\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^{k+1}|x^{k+1}\pmod N\rangle
\end{align}
$$
so if $a^r=1$ then
$$
\begin{align}
U|v_a\rangle &= a^{-1}\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^{k+1}|x^{k+1}\pmod N\rangle \\
&= a^{-1}\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^k|x^k\pmod N\rangle \\
&= a^{-1} |v_a\rangle
\end{align}
$$
and $|v_a\rangle$ is an eigenvector associated with eigenvalue $\lambda = a^{-1}$. This is reassuring, because it means that our assumption that $a^r=1$ is satisfied. It also means that $a = \exp\left(-\frac{2\pi i s}{r}\right)$. Putting it all together, we see that
$$
|u_s\rangle = |v_{e^{-2\pi is/r}}\rangle = \sum_{k=0}^{r-1}\exp\left(-\frac{2\pi isk}{r}\right)|x^k \pmod N\rangle
$$
is an eigenvector of $U$ associated with eigenvalue $\exp\left(\frac{2\pi i s}{r}\right)$ in agreement with $(5.37)$ on p.227 in Nielsen & Chuang.
