How long to program a FPGA - seconds, microseconds, less?
In my experience, it's usually one or two seconds or at least 100's of milliseconds.

It depends on how big is the FPGA and what interface (serial, parallel, etc) you use to program it.  The time remains relatively constant as FPGA technology improves because as the FPGAs get bigger, they also add new higher-speed programming interfaces.

To know for sure, divide the length of the bit stream by the bit rate of the programming interface you want to use. If you're programming from a computer host, add some time to account for the computer not devoting all its resources to filling the pipe from it to the FPGA.