> Conversely, there are uncountable "discrete" ordered sets where nothing is between a number and its two neighbours.

That's not true, and it's (relatively) easy to prove.

Consider a set S that is a subset of the reals, with the property that for each s in S there exist two numbers u and l (for "upper" and "lower") such that u < s < l and there are no numbers x for which u < x < s or s < x < l. In other words, u is the "next biggest" number and l is the "next smallest" (this formalizes the idea you've stated informally).

For each s in S, consider the radius R = min(d(s,u), d(s, l)) (of course, R, u, and l all depend on s, but reddit markdown means I'm gonna skip the subscripts). This radius is basically just the "minimum spacing" around s. Such an R exists for each s, and is strictly positive. Since R is strictly positive, so is R/2. And since the rationals are dense in the reals, we can find two rational numbers a and b (again, also dependent on s) such that s - R/2 < a < s < b < s + R/2. In other words, we can find an interval of rational numbers (a,b) that does not overlap the corresponding interval for any other s in S.

Now, consider the function f: S -> (Q x Q) that takes each element s in S and maps it onto the ordered pair of the interval generated by the process in the previous paragraph. This function is clearly injective, since none of the intervals (a,b) overlap (so they certainly cannot be the same), but the set (Q x Q) is a Cartesian product of countable sets and therefore countable. Since we have an injection from S to a countable set, S is itself (at most) countable.