This is precisely the essence of my question, given that I have little knowledge of FPGAs and have no real clue how much each reprogrammed circuit has in common with any other. :)
Very little. An FPGA is a set of reprogrammable logic blocks (LUTs) of very small size, plus a number of special purpose peripherals. The "layout" process of assigning functions to LUTs is usually done with simulated annealing and random perturbation. The compiler won't necessarily give the same output from the same input, let alone slightly different input.
The fixed-function blocks and any embedded processors (e.g. Nios) are more targetable. But you could also e.g. set up the clock PLL to leak the FPGA configuration slowly via spread-spectrum modulation.
A genetic algorithm, by contrast, encodes the system into a "string" (like a DNA strand), and then swaps pieces of strings between two "organisms," just like genetic mating does. The most optimal descendants are kept, the least are discarded, and the process is repeated. This would be harder to implement for locations, as you would have to encode locations onto a string, and be able to swap pieces of strings while maintaining the functionality of the LUTs.
Now, the FPGA is not necessarily an ideal place to insert your circuit; personally, I would put it in something like one of those flat ribbons which connect components inside so many devices, or a socket - they may have access to all the bus pins of the gadget, and they will be less conspicuous. I don't think 3D printing is the answer to this, since too many things would have to be 3D printed.
Now, I don't know how I would go about protecting from such attacks, or if this is even a real-life concern right now, but I would think that some kind of automated high-resolution X-ray imaging and analysis technology would be a more realistic direction.