So, after trying all the "logical" (to me anyway) options, like moving the box, unpair/pair etc. to no avail, I did one last desperate thing and ordered a Belkin HDMI cable, thinking I'd just end up returning it... Surprise, surprise, my remote lag is 100% gone... touch pad is totally responsive, and scrubbing is so smooth. It's been two full days now and still no degradation, so fingers crossed.
My previous HDMI was rated for 18Gbps, 4k@60Hz, and it seemed to work fine including passing 4k 60Hz DV fine. It was rated 4.5 stars on Amazon with many reviews saying it worked fine with ATV4K. But obviously something about it didn't play well with my ATV4K.
Can't really explain it, but I'm just happy my problem's gone.