Grunching, because I wanted to work it out on my own.

First problem:

One equilateral triangle in the complex plane has vertices at 0, 1 and e^(i*pi/3). (Is there a Latex editor this forum can utilise?) Call this triangle T0 - normal form for an equilateral triangle.

Now suppose we have an arbitrary equilateral triangle, T1, with integer coordinates. Assume WLOG one vertex is at the origin (we can translate to make this true). Suppose one other vertex is at a+bi for some integers a and b.

Now consider the coordinates of the normal form triangle T0 under the transformation f(z)=(a+bi)*z. This mapping is a scaling and a rotation, so it preserves equilateral triangles. One vertex of the transformed triangle is the origin, another is at a+bi. So the third point is either the third vertex of T1 or its reflection in the line from 0 to a+bi. I will assume it's the third vertex - the following argument works if it's the reflection as well.

So the third vertex is at f(e^(pi/3)), which equals e^(i*pi/3)*(a+bi). This equals a/2-b*3^.5/2+i*(b/2+3^.5/2*a).

We know the real and imaginary parts of this are integers (by assumption). The real coordinate tells us that b must be zero (given that a is an integer). If b is non-zero the answer is irrational, let alone an integer. However, then the imaginary part tells that a must also be zero, which is a contradiction as required. (If a=b=0, then T1 wasn't actually a triangle).

I have some thoughts on the second problem I'll post later.

EDIT: Now I've read the thread, my solution and Dr Straw's are the same but expressed differently. I ignored the fact a goban is rectangular rather than square, but as others noted, if the ratio is rational the proof is unaffected.

Second problem:

I think it can be done in around O(n^4). The algorithm is this:

1) Work out 3^0.5/2 to sufficient accuracy. This a bit wooly, but I think this stage is O(n) or O(n^2).
2) Consider all lines, where one vertex is at the axis and the other is at a+bi, with a and b positive and less than or equal to n. This step is O(n^2). We don't need negative mumbers since they will give the same answer.
3) For a give a+bi, work out the coordinates of the point making an equilateral triangle using the approximation at step 1 and the formula from my previous post.
4) Find the 4 (say - 6 may actually be needed) integer points nearest the equilateral point found at point 3.
HYPOTHESIS: One of these 4 points mimimises the triangle metric given the base line. I haven't actually proved this, since I'm lazy, but it feels intuitively plausible. This is quick.
5) We now have 4 triangles whose metric we should assess. Run over them in turn. See if any of them are scale multiples of earlier triangles checked. If they are, dsiscard them (we already know the metric). I think this step is O(n^2).
6) Find the metric for the triangle considered. I'm not sure of the comlexity of this step, but O(n^2) sounds like a good guess.

So overall, the number of lines is O(n^2) and we do a calc of complexity around O(n^2) fpr each point. So this seems to be around O(n^4). The key missing bit is proving my hyothesis.

EDIT: This is the same as Perceval's revised estimate of the complexity. The difference is that I've allowed for evaluating the triangle metrix to sufficient accuracy, which I think must have non-zero cost.