Is the basis in which the density matrix diagonal an orthogonal basis?
Note that if the density operator is $1/N$ times the identity, then it is diagonal in every basis. On the other hand, every density operator on a finite dimensional Hilbert space is diagonal in an orthonormal basis: this follows from the spectral theorem, which asserts that this is exactly equivalent to require that the operator is hermitian. In general you can write the density operator in a unique way as a sum: $$\hat \rho = \sum _i \lambda _i \hat P _i,$$
where $\hat P _i$ is the projection on the eigenspace $\Lambda _i$ of the eigenvalue $\lambda _i$, the $\lambda _i$'s are distinct, $0\leq \lambda _i$ and $\sum _i \lambda _i \cdot \text {dim} \Lambda _i =1$. Then, you can arbitrarily fix an orthogonal basis on each $\Lambda _i$ and assign to each vector of such a basis the weight $p_i=\lambda _i$.
How do I find it's lower bound?
You want to prove that: $$\sum _{i=1}^N p_i^2 \geq 1/N$$ where $$\sum _{i=1}^Np_i=1.$$
The simplest method is to apply Jensen's inequality with the convex function $x\mapsto x^2$, to the sum $\sum _i p_i/N$ ($1/N$ being the weight of $i$):
$$\dfrac{1}{N^2}=(\sum _i \dfrac{p_i}{N})^2\leq \dfrac{1}{N}\sum _i p_i ^2.$$
As an alternative method (which is far more general), you can apply Lagrange's multipliers theorem: it states that a necessary condition for a local minimum of a smooth function $f\colon \mathbb R ^N \to \mathbb R$, restricted to a smooth submanifold $M$ of $\mathbb R ^n$, is that $\nabla f(x_0)\perp T_{x_0}M$ at the point of minimum $x_0$.
Define $$\overline M_N =\{(p_1,\dots,p_N)\in \mathbb R ^N \,\, \sum _i p_i =1, \,\, 0\leq p_i \leq 1\}.$$ Since $\overline M _N$ is compact, $f(\{p_i\})= \sum _i p_i ^2$ has a minimum in $\overline M _N$. First, assume that the minimum lies in the interior $M_N$ of $\overline M _N$. Then, Lagrange's theorem states that, at the minimum: $$\nabla f=(p_1,p_2,\dots,p_N)\propto (1,1,\dots,1),$$
which, together with $\sum _i p_i =1$ gives $p_i=1/N$ and $\sum _i p_i^2=N(1/N)^2=1/N$.
Now, if $N=1$ the lower bound is trivial. By induction, we see that on the boundary of $\overline M _N$, $f$ is lower bounded by $1/(N-1)$, so the minimum is actually in the interior $M _N$. This completes the proof.
