bridge the modem and get yourself a decent router. don't use whatever they gave you.
also if the modem is in a shitty location this will let you move the router to somewhere better

Since all other applications in the house have no internet issues at all, I find it difficult to believe the fault is with the Modem (Although I'm sure it sucks). I suspect it's a setting issue with my laptop.

How old is the laptop

4 years.

In the mean time, the company turned the All-In-One box' internet off in an attempt to "decrease background noise for the modem". It didn't change a thing