I did try the flushing, to no avail, but I downloaded a free DNS benchmark tool (
http://www.grc.com/dns/benchmark.htm), and it found that Shaw's DNS were by far the fastest to respond (compared with Google, Open DNS, 4.2.2.x, etc.). I think the problem is when the router acts as a DNS server, it drops to near the bottom of the list in terms of performance, so that's likely the source of my lag.
I think that I'll change each PCs network settings to hit the Shaw DNS directly instead of using the router as a middleman and see if that helps.