Is there any way to ping any other host on your network (e.g., your gateway, or another computer), to eliminate most other sections of your network?

It sounds like you need to convince your ISP that the problem is with their connection, not your network. To do that, remove as much of your network as possible - try using a wired connection directly to the cable modem. If that has the same symptoms, have the cable company come out and help you troubleshoot. There's not a lot more you can do there.

- Pete