LOOOONG Delays - "Resolving Host"

My first thought was to suggest flushing your DNS cache by running the command "ipconfig /flushdns" as administrator on your, presumably, Windows-based devices. However, upon further reading, it sounds like the issue began affecting multiple devices simultaneously.

If you are fortunate enough to have a modem that offers an expanded look at your error logs and other connection-related data through the 192.168.100.1 (or similar)  web interface, you might want to look there for things like frequent T3 timeouts, correctable and most-importantly uncorrectable codeword numbers that are frequently accumulating on any of your downstream channels.  In addition, you should be able to see if your modem channel signal levels and SNR numbers are within spec.  Lastly, if your modem and router are separate, verify your connection speed and duplex setting between them.  Good luck.