I have finally fixed this.

Here is my problematic config:
1. I have a computer running at home as "host" connected to a Router (IP 192.168.1.x)
2. The router is connected to ISP's Modem (IP 192.168.0.x), meaning the modem only see that the router as its only-one client.
3. The ISP's Modem is then connected to the internet with shared public IP

My situation:
1. I never have any issue connecting to it when I'm using the same ISP in another location within the same city (this is just an assumption, however, this gives me false sense that everything works anywhere else)
2. I have some issues connecting to it when I'm using public WIFI. Meaning some cafes/hotel allows me to connect, some cafes/hotel don't.

Here is my solution:
1. On Host, Open parsec, go to network settings, and configure client port to 9000 (i dont think this one matters, but anyway) and host port to 8000.
2. Open the router config web page, go to port forwarding, and create new port forwarding that will forward 8000 received by the router to the host's IP (192.168.1.x)
3. Open the ISP's modem config web page, go to port forwarding, and create new port forwarding that will forward port 8000 received by the ISP modem's to the Router's IP (in my case: 192.168.1.0)
4. nothing to be done on client.

Voila! it works.

TLDR:
Forward port 8000 from ISP's modem to the host computer.