OK so this is kind of an odd situation. Your ISP has cleared your broadband connection as not being the problem and while troubleshooting the issue you have two devices that work as normal and two devices that don't. (With three of them from different manufacturers, so that at least rules out one issue.)
So maybe the focus should be on your home WiFi network. As you referred to your ISP replacing the router that implies you've got one of those combined modem/router boxes, as opposed to a separate, ISP-supplied modem and your own wireless router. That limits your own control over your home network as most ISPs don't generally want to give their own customers that much flexibility compared to if you had your own router. In either case, try this test on your S3, M8, and S5. Using whichever browser on each go to:
http://speedof.me
It's just a HTML5 based broadband speed test site. Don't do them simultaneously, do each phone sequentially, and you'll get better results if no one is actually doing anything on your home network (i.e. if someone is watching Netflix in another room that will throw off your test results quite a bit).
Jot down the broadband speed, or bandwidth, and latency numbers for each phone. Bandwidth is measured in Mbps (Megabits per second) and latency is measured in ms (milliseconds). Usually the bandwidth is the more common element that gets consideration but in this instance take note of your latency numbers. Do all three phones have roughly the same latency numbers or is there a wide range?
Also, you might also want to install this Netalyzr app from U.C. Berkeley:
https://play.google.com/store/apps/details?id=edu.berkeley.icsi.netalyzr.android&hl=en
Run a test on your home network and in the test results the items it checks will be highlighted in green, yellow, and red. Pay attention to the things in yellow and red and read the explanations that accompany of them. There might be an indicator as to something specific that will at least explain the mystery.
Offhand I'd suggest you try resetting your modem/router to its factory default settings and then reconfigure it to suit your home networking needs accordingly. This is something of a long read, and a lot of it probably won't even apply to your situation but take a look at this multi-part home networking guide:
http://lifehacker.com/5833254/know-your-network-the-complete-guide