After a lot of research it seems the real villain was Norton, which was included with our laptops when we bought them. Seems some process or other had survived the uninstall (this was ages ago, when installing AVG), and decided to go for a comeback when it noticed AVG was gone. Uninstalled it again, and although it gave me an error at the end and pointed me to a page that wouldn't load, things seem to be working now. Internet is back up again, Avast updates and the trouble my brother had with finding servers when playing Team Fortress through Steam is also gone.
Edit: went to Remove Programs again, just to check, and to my dismay Norton was still listed! But this time, when trying to uninstall, I was told the app seemed to be uninstalled already, and given the option to remove it from the list. Which I agreed to. Hopefully it is gone for good.