jc's answer touches most of the bases. Let me just clear up a few points.

You can, in fact, give concrete bounds on the probability a graph with vertices chosen from a finite grid will fail to be generic for the purposes of rigidity, as jc alluded to. The relevant theorem is called the Schwartz-Zippel(-DeMillo-Lipton) Lemma. Namely, suppose you are given a non-zero polynomial $P(x_1,\dots,x_n)$ of degree $d$ over some field $F$, and a finite subset $S$ of $F$. Then the probability that $P$ is zero when evaluated on arguments chosen uniformly at random from $S$ is zero at most $d/|S|$. This gives an easy randomized algorithm for testing whether a polynomial is zero or not, given bounds on the degree. (Lipton wrote up a nice history.)

The test for local rigidity boils down to checking the rank of the rigidity matrix (the Jacobian of the length function), which can in turn be interpreted as checking whether a certain polynomial is zero. Concretely, in my paper with Healy and Gortler we go through the analysis and get specific bounds (in Section 5). We also go through some analysis for global rigidity, but it's for whether the check for generic global rigidity works, not whether the particular framework is actually globally rigid. For concrete bounds there, you'd have to do a little more work.

(While I was writing this, my co-author Steven Gortler posted his own answer, but we cover different points so I'm leaving this up.)

I think the question about global rigidity is well-answered by now. The question also asked about algorithms for finding the realization. It sounds like the graphs are pretty dense, dense enough that they're likely to be universally rigid: the edge lengths will determine the positions in any dimension, not just 2 dimensions. (For instance, the square of any 3-connected graph is 3-connected.) For such graphs, there is a good algorithm, namely semidefinite programming: Consider the Gram matrix of the configuration, the positive semi-definite matrix formed by dot products between the coordinates. The length constraints give linear constraints on such matrices. If the graph is universally rigid, there will be essentially one PSD matrix satisfying the constraints; this gives you the embedding. This kind of problem (a PSD matrix with linear constraints) can be solved quickly, at least in practice.

jc's answer touches most of the bases. Let me just clear up a few points.

You can, in fact, give concrete bounds on the probability a graph with vertices chosen from a finite grid will fail to be generic for the purposes of rigidity, as jc alluded to. The relevant theorem is called the Schwartz-Zippel(-DeMillo-Lipton) Lemma. Namely, suppose you are given a non-zero polynomial $P(x_1,\dots,x_n)$ of degree $d$ over some field $F$, and a finite subset $S$ of $F$. Then the probability that $P$ is zero when evaluated on arguments chosen uniformly at random from $S$ is zero at most $d/|S|$. This gives an easy randomized algorithm for testing whether a polynomial is zero or not, given bounds on the degree. (Lipton wrote up a nice history.)

The test for local rigidity boils down to checking the rank of the rigidity matrix (the Jacobian of the length function), which can in turn be interpreted as checking whether a certain polynomial is zero. Concretely, in my paper Characterizing Generic Global Rigidity with Healy and Gortler (published version) we go through the analysis and get specific bounds (in Section 5). We also go through some analysis for global rigidity, but it's for whether the check for generic global rigidity works, not whether the particular framework is actually globally rigid. For concrete bounds there, you'd have to do a little more work.

(While I was writing this, my co-author Steven Gortler posted his own answer, but we cover different points so I'm leaving this up.)

I think the question about global rigidity is well-answered by now. The question also asked about algorithms for finding the realization. It sounds like the graphs are pretty dense, dense enough that they're likely to be universally rigid: the edge lengths will determine the positions in any dimension, not just 2 dimensions. (For instance, the square of any 3-connected graph is 3-connected, see On affine rigidity, published version.) For such graphs, there is a good algorithm, namely semidefinite programming: Consider the Gram matrix of the configuration, the positive semi-definite matrix formed by dot products between the coordinates. The length constraints give linear constraints on such matrices. If the graph is universally rigid, there will be essentially one PSD matrix satisfying the constraints; this gives you the embedding. This kind of problem (a PSD matrix with linear constraints) can be solved quickly, at least in practice.