We will show that the desired $C$ is the positive root of the equation $x^2 + x = 1$, $C = \frac{\sqrt{5}-1}{2}$.

First, suppose that for some positive integers $x < y$ the inequalities $\sqrt{x^2 + 2y} > C$, $\{\sqrt{y^2 + 2x}\} > C$ hold. Note that $y^2 < y^2 + 2x < (y + 1)^2$, so we have $y^2 + 2x > (y + C)^2 \Leftrightarrow 2x > 2Cy + C^2 \Rightarrow x > Cy$. Then $(x+1)^2 < x^2 + 2y < x^2 + \frac{2}{C}x < x^2 + 4x < (x+2)^2$.

So $x^2 + 2y > (x + 1 + C)^2 \Leftrightarrow 2y > 2(C + 1)x + (C + 1)^2 \Rightarrow y > (C + 1)x$.
But then $xy > xy \cdot C(C + 1) = xy$: a contradiction.

Now let's show that any $C_1 < C$ does not satisfy the condition. Consider $y = [(C + 1)x]$ for some sufficiently large $x$.
We show that starting from some $x$ we have $\sqrt{x^2 + 2y} > C_1$, $\sqrt{y^2 + 2x} > C_1$.
It is easy to see that $y^2 < y^2 + 2x < (y + 1)^2$ and also $(x + 1)^2 < x^2 + 2y < (x + 2)^2$ so it suffices to show that for sufficiently large $x$ it holds that $x^2 + 2y > (x + 1 + C_1)^2$, $y^2 + 2x > (y + C_1)^2$. These inequalities are equivalent to the following:
$2y > 2x(C_1 + 1) + (C_1 + 1)^2$, $2x > 2yC_1 + C_1^2$. Note that $2y - 2x(C_1 + 1) \ge 2x(C + 1) - 2 - 2x(C_1 + 1) = 2x(C - C_1) - 2$ which is greater than $(C_1 + 1)^2$ for a sufficiently large $x$. Also note that $2x - 2yC_1 < 2x - 2x(C + 1)C_1 = x(2 - (C + 1)C_1)$. Since $(C + 1)C_1 < (C + 1)C = 1$, this value is greater than $C_1^2$ for a sufficiently large $x$.