Mathematicians have very precise definitions for terms like "infinite" and "same size". The single unambiguous correct answer to this question is that using the standard mathematical definitions, the rationals have the "same size" as the integers.
First, here are the definitions:
Define "$0$" = emptyset, "$1$" $= \{0\}$, "$2$" $= \{0,1\}$, "$3$" $= \{0,1,2\}$, etc. So, the number "n" is really a set with $n$ elements in it.
A set $A$ is called "finite" iff there is some $n$ and a function $f:A\to n$ which is bijective.
A set $A$ is called "infinite" iff it is not finite. (Note that this notion says nothing about "counting never stops" or anything like that.)
Two sets $A$ and $B$ are said to have the "same size" if there is a function $f:A\to B$ which is a bijection. Note that we do NOT require that ALL functions be bijections, just that there is SOME bijection.
Once one accepts these definitions, one can prove that the rationals and integers have the same size. One just needs to find a particular bijection between the two sets. If you don't like the one you mentioned in your post, may I suggest the Calkin-Wilf enumeration of the rationals?
Of course, these give bijections between the naturals (without $0$) and the rationals, but once you have a bijection like this, it's easy to construct a bijection from the integers to the rationals by composing with a bijection from the integers to the positive natural numbers.
I am going to replace some definitions by obviously equivalent ones. The benefit will be that the proofs are easier to understand. I am writing down very detailed proofs that you would not normally find in a college-level math textbook.
Definition: For $n \in \mathbb{N}$ define $[n] = \{k \in \mathbb{N} \mid k < n\}$.
Definition: The image of a map $f : X \to Y$ is the set $\mathrm{im}(f) = \{y \in Y \mid \exists x \in X \,.\, f(x) = y\}$.
Definition: A set $X$ is infinite when for every $n \in \mathbb{N}$ and every map $f : [n] \to X$ there is some $x \in X$ which is not in the image of $f$.
Lemma 1: An infinite set $X$ contains an element.
Proof. Because $X$ is infinite there is $x \in X$ which is not in the image of the unique map $[0] \to X$. QED.
Lemma 2: If $X$ is infinite then there exists a map $c$ such that $c(n,f) \in X \setminus \mathrm{im}(f)$ for every $n \in \mathbb{N}$ and every $f : [n] \to X$.
Proof. For every $n \in \mathbb{N}$ and $f : [n] \to X$ the set $X \setminus \mathrm{im}(f)$ contains an element because $X$ is infinite. By the axiom of choice there exists a choice map $c$ such that $c(n,f) \in X \setminus \mathrm{im}(f)$ for all $n$ and $f$. QED.
Here is an informal explanation of the map $c$. Given an infinite set $X$ and any elements $x_0, \ldots, x_{n-1} \in X$, we may view the tuple $(x_0, \ldots, x_n)$ as a map $f : [n] \to X$ where $f(k) = x_k$. By a slight abuse of notation we can then write $c(n,f)$ as $c(x_0, \ldots, x_{n-1})$. Now we see that $c$ accepts finitely many elements of $X$ and returns an element in $X$ which is different from all of them.
Proposition 1: If $X$ is infinite then there exists an injective map $i : \mathbb{N} \to X$.
Proof. By Lemma 1 there is $x \in X$ and let $c$ be the map from Lemma 2. Define $i$ by recursion:
\begin{align*}
i(0) &= x \\
i(n) &= c(i(0), \ldots, i(n-1)) \qquad\qquad \text{for $n \geq 1$}
\end{align*}
Clearly, $i$ is injective because $i(n)$ is chosen so that it is different from $i(0), i(1), \ldots, i(n-1)$. QED.
Proposition 2: If $X$ is infinite then it is in bijection with some proper subset $Y \subseteq X$.
Proof. Suppose $X$ is infinite. We seek a proper subset $Y \subseteq X$ and a bijection $f : X \to Y$. Let $i$ be the map from Proposition 1. Define
$$Y = X \setminus \{i(0)\}$$
and define $b : X \to Y$ by
$$b(x) = \begin{cases}
x & \text{if $x \not\in \mathrm{im}(i)$}\\
i(n+1) & \text{if $x = i(n)$ for a (unique) $n \in \mathbb{N}$}
\end{cases}
$$
in words, $b$ takes $i(0)$ to $i(1)$, $i(1)$ to $i(2)$, and so on, and does not move elements which are outside the image of $i$. Clearly, $b$ is injective because $i$ is. It is surjective because the only element not in the image of $b$ is $i(0)$. QED.
Proposition 3: If $X$ is a set and $b : X \to Y$ a bijection from $X$ to a proper subset $Y \subseteq X$, then there is an injective map $j : \mathbb{N} \to X$.
Proof.
Because $Y$ is a proper subset there exists $x \in X \setminus Y$. We define a map $j : \mathbb{N} \to X$ by recursion:
\begin{align*}
j(0) &= x \\
j(n) &= b(j(n-1)) \qquad\qquad\text{for $n \geq 1$}
\end{align*}
To prove that $j$ is injective, it suffices to verify that $j(m) \neq j(n)$ for all $m < n$. We do this by induction on $m$:
if $m = 0$ then $j(0) = x$ is different from $j(n) = b(j(n-1))$ because $b(j(n-1)) \in Y$ and $x \not\in Y$.
for the induction step, suppose we had $j(m) = j(n)$ for some $0 < m < n$. Then we would have $b(j(m-1)) = j(m) = j(n) = b(j(n-1))$ and because $b$ is a bijection it would follow that $j(m-1) = j(n-1)$, which is impossible by the induction hypothesis for $m-1$. Therefore it must be the case that $j(m) \neq j(n)$.
QED.
Theorem: A set is infinite if, and only if, it is equipotent with some proper subset.
Proof.
If $X$ is infinite then we apply Propostion 2 to get a proper subset $Y \subseteq X$ which is equipotent with $X$.
Conversely, suppose we have a bijection $b : X \to Y$ for a proper subset $Y \subseteq X$. By Proposition 3 there is an injective map $j : \mathbb{N} \to X$. To see that $X$ is infinite, consider any $n \in \mathbb{N}$ and $f : [n] \to X$. There are $n+1$ distinct elements $j(0), j(1), \ldots, j(n) \in X$, and so at least one of them is not in $\mathrm{im}(f)$ because $\mathrm{im}(f)$ has at most $n$ elements. QED.
Best Answer
If you know that square-roots exist, you can just pick any $x$ in the interval $[a-\sqrt{D},a+\sqrt{D}]$ and then show that you can find a $y$ that satisfies the equation for each $x$. In higher dimensions, you can reduce to two dimensions by setting all but two of the squared terms to zero.
So the question boils down to how do you know $[a-\sqrt{D},a+\sqrt{D}]$ is infinite if $\sqrt{D} > 0$? There are a number of elementary ways of showing this, for example in between any two different real numbers there is a rational number strictly in between.