Lower bound the difference between distinct values of a function over a discrete domain?
You can certainly do better than $N(N-1)$: you can achieve $O(N \lg N)$ running time.  Evaluate $f$ on every possible element of $x$, then sort the resulting values, and look at the gap between consecutive values.  The smallest such gap is exactly the value of $\min |f(x_1)-f(x_2)|$.

As Raphael says, without any information about $f$, it seems unlikely that you can do any better than to evaluate $f$ on every possible input.  Indeed, it seems possible to prove this using an adversarial argument, in a black-box setting: if there is a single value $x^*$ where you haven't evaluated $f(x^*)$, then any answer your algorithm outputs can be made to be wrong by choosing the value of $f(x^*)$ appropriately.

Since the notion of "monotonically non-decreasing" is not defined when the domain is not totally ordered (as in your example for $X$), and the notion of continuous is not defined when the domain is discrete (i.e., not continuous, as in your example for $X$), your second question isn't well-formed and can't be answered in its current state.