Answer: $\min p = F_4 = 2^{16} + 1$.
It is known that Fermat's number $F_4$ is prime. It is easy to verify that $\{\sqrt{F_4}\} < \frac{1}{501}$. Indeed, the latter inequality is equivalent to $\sqrt{2^{16} + 1} - 256 < \frac{1}{501}$, i.e. $\frac{1}{\sqrt{256^2 + 1} + 256} < \frac{1}{501}$ which follows from $\frac{1}{2 \cdot 256} < \frac{1}{501}$. So, $F_4$ satisfies the condition of the problem.

Now let $p < F_4$; we prove that the inequality
$$\{\sqrt{p}\} < \frac{1}{501} \quad (*)$$
is impossible. Indeed, let $n^2 < p < (n+1)^2$, then $p = n^2 + a$ where $1 \le a \le 2n$. Then $[\sqrt{p}] = n$, hence
$$(*) \Leftrightarrow \sqrt{n^2 + a} - n < \frac{1}{501} \Leftrightarrow n^2 + a < n^2 + \frac{2n}{501} + \frac{1}{501^2} \Leftrightarrow n > \frac{501}{2}a - \frac{1}{1002}.$$
If $a \ge 2$ then $n \ge 500 \Rightarrow p > F_4$ — a contradiction. So, $a = 1$ and $n \ge 251$, i.e. $p \ge 251^2+1$. Note that $251^2+1, 251^2+3, 251^2+5$ are even, so are not prime. Further, $252^2+1$ is composite, since it is divisible by 5. Finally, show that $254^2+1$ is divisible by 149. We have the following chain of congruences modulo 149:
$$254^2 + 1 \equiv (-44)^2 + 1 \equiv \frac{132^2 + 9}{9} \equiv \frac{17^2 + 9}{9} \equiv \frac{298}{9} \equiv 0 \pmod{149}.$$
Thus $254^2 + 1$ is composite, so $p = 256^2 + 1$ is minimal possible.