Well, that turned to be totally my fault.
DNS servers list in dhcpd.conf on the wifi router machine was quite outdated with the first entry being dead.
The DNS lookup was processed linearly through the list with the proper timeout hang on the first entry.
Upon fixing that list, now everything seems smooth.
Thanks for the hints!
ps: interesting enough that both systemd'ed linux machines and windows ones managed to insensibly ignore the problem, provided with a list of three different DNS IPs, first being dead.
Indeed this looks like name resolution delays.
You need to check what domain name server your config queries and how
quickly that responds to the DNS queries. Are there multiple servers
listed in /etc/resolv.conf? Or does that file differ in the good vs.
the bad situation?
You can direct queries to a special DNS server like:
dig google.com @server
or
host google.com server