Same problem with two providers would suggest the problem isn't with the provider.
Same problem with multiple devices would suggest the problem isn't with your equipment.
What is left is the wiring within your home. A loose connection, a bad connector, or damaged cable. My guess is that when FIOS was installed they connected to a junction box and used the existing house wiring. The easiest way to verify that would be to run a temporary cable from the junction box to the router.