I've had this problem on-and-off, which makes it hard to diagnose. However I think I finally fixed it (now it'll start happening again, of course).
1) I have an amp/splittter/signal cleaner as my main splitter. I know the amp part isn't necessary with FIOS, but the cleaner seems to make a difference for me.
2) For the S3 in my HT, which is closest to the split (i.e. least attenuation from the cable length), I added a -7db splitter right in front of the Tivo, just to attenuate the signal some more. When I did it at the splitter, this didn't help as much.
3) For the THD in my bedroom, I replaced the crappy RG59 with a new RG6QS and crimp connectors (something that's everywhere else, I just never did it there).
It seems that both boxes are now working well, although again this is a hard thing for me to test as it's sporadic at best. However HBOHD on my S3 was very often pixelated, and it hasn't been since I did this, and SHOTOO was also often pixelated on my bedroom, and it hasn't been since.
Who knows if this really fixed it, or if Verizon did something at the same time...