Using TexMaker and having installed MikTeX, where I opted to install missing packages on the fly (even 'untested' ones), I still find I don't have the packages. I tried to verify the connection source (as suggested here: MikTeX 2.9, install packages on the fly?), however I already have "random" selected and am using Windows 10 — meaning I'm using the MikTeX console rather than the MikTeX maintenance program suggested above. Other resources are specific to Ubuntu (miktex does not autoinstall via texmaker) or vague, or both.
I'm able to compile a dummy TeX file (like 'Hello World') but nothing requiring packages. Obviously the best solution would be to [automatically] download packages as I include them in documents, but a good workaround would be to download a big repo of common packages (that way Anaconda does for Python, for example).
Some specs:
Windows 10
MikTeX 2.9.6637
TexMaker 5.0.2
Best Answer
My best guess is that you are probably behind a proxy that relays all traffic that goes to the internet. Ask your local IT-experts for the proxy's IP-address and port and then goto
Miktex Package Manager -> Repository -> Connection Settings
Set the checkbox at "Use a proxy server" and enter the address and port. If the proxy-server requires authentication (try with and without), set the other checkbox "Authentication required" as well.