I know that everytime when thunderbird makes updates it starts asking me for password for all the accounts, which is totally idiotic. I must provide and actually change the password for every account we have.

I haven't heard of or seen such with my several personal Gmail accounts. Are you using OAuth2 authentication?

Must I put it explicitly on thunderbird? Or in Gmail web?

Check out Automatic Conversion of Google mail accounts to OAuth 2.0 Authentication

OK, what I have seen else that I put my router ASUS RT-N12 and speed was varying from 144Mbps to 26.0 Mbits which was totally unacceptable. I bought TP-Link Archer C6 and now messages are downloaded, but shown after 3-4 mins. You see the header in the inbox but when you click, you wait 3-4mins. Before, you have to restart the Thunderbird to show them. ISP speed is 300Mbps, I'm from Bulgaria, so it's local provider. Offcourse not to everywhere you get this speed. I have also Panda Adaptive defense 360 installed. I don't now if this antivirus stops something, or makes slow something. OAuth2 is automatically configured and everytinh else is as it should be from your links.

I saw one more thing - we have messages from 2013. One account for example between 2013 and 2018 has 70 k messages overall. Could this be the reason for slowness? Antivirus Is panda adaptive defense and there is realtime protection I think that all emails are being downloaded and checked constantly and this might be the reason.

Ive started rebuilding global database on all 3 computers. I've put some value in cache also, we'll see on Monday if that works. There is some improvement.

I'm not familiar with that Panda product, but the general concensus is you should add Thunderbird's profile folder to your security software's exclusions list, and add Thunderbird itself as a trusted program so that its normal functioning is not interefered with by said software. Also, if your security software allows it, disable scanning of encrypted email traffic. There is a long history of antivirus programs messing with Thunderbird, so this is something you need to address as well.

If OAuth2 tokens issued to Thunderbird keep expiring and you're forced to reauthenticate often, then something could be clearing cookies used by Thunderbird, and these cookies are used for the OAuth2 process to stick. A third-party PC cleanup or "optimization" utility could be doing this in the background. It could be a recently installed program, or even part of your antivirus.

Another cause for slowdowns is Gmail's bandwidth limits. See https://support.google.com/a/answer/1071518?hl=en for details. You can avoid hitting those limits by downloading headers only since you have tens of thousands of messages.

You don't need messages as old as 2013 to be synchronised (downloaded in full for offline access) by Thunderbird, do you? You can limit the age (and size) of messages to be downloaded and Thunderbird's storage footprint on your system to significantly speed things up. You will find these settings in Account Settings, for each account.

Do you mean that thunderbird is syncing these mails from 2013 constantly? But they're already downloaded before and are stored. If they are kept online they will be also synced? So I can limit the age of the messages which are synced even though they're online?