OK, I think that it is solved, and the winner is . . . the cable.
I thought that I had tested the cable aspect, but clearly not well enough.
(Just before this, I did put in an Intel gigabit NIC, and it was even worse than my built in Ethernet with respect to taking a long time to connect.)
The weird thing is that the previous cable does connect up (after 10 seconds), and transmission speeds and latency are fine. Using the previous cable on a device that doesn't have a gigabit Ethernet gives no problem at all with linking -- it's nearly instantaneous like I'm used to. It is a cat 5 cable, so should work, but maybe some of the wires not used for 100base-T but are used for 1000base-T are faulty. I think that I have a cable tester around somewhere. I'll see if I can find it to investigate.
Thanks, everyone, for your thoughts and recommendations.
My apologies for using up folks' time when I should have not blown it on my cable testing.