If $(1) \;\; {\displaystyle \sum_{x=1}^n} \sqrt{x^2+1} \leq \frac{n(n+p)}{2}$ for all natural numbers $n$, then $p_{min} = 2\sqrt{2}-1$. Proof: According to (1) $(2) \;\; \sum_{x=1}^n (\sqrt{x^2+1} - x) \leq \frac{n(n+p)}{2} - \sum_{x=1}^n x = \frac{n(n+p)}{2} - \frac{n(n+1)}{2} = \frac{n(p-1)}{2}$, By defining $(3) \;\; S_n = \frac{1}{n} {\displaystyle \sum_{x=1}^n} (\sqrt{x^2 + 1} - x)$, and applying this definition on inequality (2), we obtain $(4) \;\; p \geq 2S_n + 1$ for all $n>0$. Moreover, by (3) $nS_n = {\displaystyle \sum_{x=1}^n (\sqrt{x^2 + 1} - x) = \sum_{x=1}^n} \frac{1}{\sqrt{x^2 + 1} + x} > {\displaystyle \sum_{x=1}^n} \frac{1}{(x + \frac{1}{2x}) + x} = {\displaystyle \sum_{x=1}^n} \frac{2x}{1 + 4x^2}$, implying $(5) \;\; S_n > \frac{1}{2n}$ for all $n>1$. Futhermore $S_n = -\frac{1}{n} {\displaystyle \sum_{x=1}^n} x + \frac{1}{n} {\displaystyle \sum_{x=1}^n} \sqrt{x^2 + 1} = -\frac{n+1}{2} + \frac{1}{n}{\displaystyle \sum_{x=1}^n} \sqrt{x^2 + 1}$. Hence $(6) \;\; {\displaystyle \sum_{x=1}^n} \sqrt{x^2 + 1} = nS_n + \frac{n(n+1)}{2}$. Therefore \begin{eqnarray*} (n-1)S_{n-1} & = & {\textstyle -\frac{n(n-1)}{2}} + \sum_{x=1}^{n-1} \sqrt{x^2 + 1} \\ & = & {\textstyle -\frac{n(n-1)}{2}} - \sqrt{n^2 + 1} + \sum_{x=1}^n \sqrt{x^2 + 1} \\ & = & {\textstyle -\frac{n(n-1)}{2} - \sqrt{n^2 + 1} + \frac{n(n+1)}{2}} + nS_n \\ & = & n - \sqrt{n^2 + 1} + nS_n. \end{eqnarray*} yielding $S_n = -1 + \frac{1}{n}\sqrt{n^2+1} + (1 - \frac{1}{n})S_{n-1}$. For $n>1$ we define $T_n = S_{n-1} - S_n$. Then by (6) $T_n = 1 - \frac{1}{n}\sqrt{n^2+1} + \frac{S_{n-1}}{n}$, which combined with ineqality (5) result in $T_n > 1 - \frac{1}{n}\sqrt{n^2+1} + \frac{1}{2n(n-1)} > 1 - \frac{1}{n}\sqrt{n^2+1} + \frac{1}{2n^2}$. Hence $T_n>0$ for all $n>2$ since ${\textstyle (1 + \frac{1}{2n^2})^2 > (\frac{\sqrt{n^2+1}}{n})^2}$. From (3) we obtain $S_1 = \sqrt{2}-1$ and ${\textstyle S_2 = \frac{\sqrt{2} + \sqrt{5} - 3}{2}}$, yielding $T_2 = S_1 - S_2 = {\textstyle \frac{\sqrt{2} - \sqrt{5}+1}{2}> 0}$. Thus $T_n = S_{n-1} - S_n > 0$ for all $n>1$, i.e. the sequence $\{S_n\}_{n=1}^{\infty}$ is strictly decreasing. This fact combined with inequality (4) give us $p_{min} = 2S_1 + 1 = 2(\sqrt{2} - 1) + 1 = 2\sqrt{2} - 1$. $\;\;$ q.e.d.

Does this works? Answer is $p=2\sqrt{2}-1$. Check $n=1, 2,3$ (maybe not important) Note that $\sqrt{k^2+1}<k+\frac{1}{2k}$, so $LHS<\sqrt{2}+\sum_{k>1} (k+\frac{1}{2k}) = \sqrt{2} + \frac{n(n+1)}{2} + \frac{1}{2} \sum_{k=1}^{n} \frac{1}{k} -\frac{3}{2} < \frac{n(n+1)}{2}+\frac{1}{2}H_n <^? \frac{n(n+2\sqrt{2}-1)}{2}$ or $1/2H_n <^? n(\sqrt{2} -1)$ which is true for $n>3$ (easy to see by induction).

We claim $p=2\sqrt2-1$. For $n=1$, we must have $\sqrt2\leq\frac12(1+p)$, so $p\geq2\sqrt2-1$. Now, we will show $p=2\sqrt2-1$ works. We have $\sqrt{n^2+1}\leq n+\sqrt2-1$, so $\sum_{i=1}^n\sqrt{i^2+1}\leq\sum_{i=1}^ni+\sqrt2-1=\frac{n(n+1)}2+(\sqrt2-1)n=\frac12n(2\sqrt2-1)$.