And one more quick update. Even using 2.4 GHz network, Fire Stick was still struggling sometimes. In the middle of watching something, it would lose connection. Everything else in the same room works without any problem, either on 5 Ghz, or 2.4 GHz network.
I purchased one of those wifi extenders (2.4 GHz only) and now Fire Stick seems to be working without any issues. The "extended" wifi signal is about 15-20 dBm stronger than the regular 2.4 GHz network. It is typically around 30-35 dBm, versus 50-ish dBm, without the boost. While even 50-60 dBm should be more than enough for smooth streaming, obviously Fire Stick needs much stronger signal. Why is that so, I don't know, but I hope I have solved the problem...unfortunately, with some more money spent.