Here's an approach based on finding all right angled triangles with a hypotenuse <=500 and measuring the perimeters. The answer is the Commonest perimeter which is less than 1000. This runs in about 1 second.

rats[n_] := DeleteDuplicates[ Cases[Divisors[n^2, GaussianIntegers -> True], z_Complex /; Abs[z] == n :> Sort[{Re@z, Im@z, n}]]]; Commonest[Select[Flatten[Table[Total[rats[h], {2}], {h, 5, 500}]], 0 < # <= 1000 &]] (* 840 *) 

Here's an approach based on finding all right angled triangles with a hypotenuse <=500 and measuring the perimeters. The answer is the Commonest perimeter which is less than 1000. This runs in about 1 second.

rats[n_] := DeleteDuplicates[ Cases[Divisors[n^2, GaussianIntegers -> True], z_Complex /; Abs[z] == n :> Sort[{Re@z, Im@z, n}]]]; Commonest[Select[Flatten[Table[Total[rats[h], {2}], {h, 5, 500}]], 0 < # <= 1000 &]] (* 840 *) 

Update

It is a bit faster to use PowersRepresentations to get the right angled triangles. Here is the solution as a one-liner:

Commonest[Select[ Flatten[# + Total[Rest@PowersRepresentations[#^2, 2, 2], {2}] & /@ Range[500]], 0 < # <= 1000 &]]