From my (limited) experience RDP is significantly better than VNC in terms of sluggishness and glitches. The second thing is that both VNC and RDP will try to transmit those parts of the screen that changed since the last frame rather than simply sending full "screenshots" for every frame. As a result the final effect highly depends on what are you using the remote desktop for.

Since my work is mainly coding in IDE and working with several ssh sessions, I almost exclusively work with text which is much easier for a great remote desktop experience. On the other hand, when I tried watching videos over remote desktop it was really bad.

The other things that you might consider is UDP vs. TCP, especially since some routers can handle long UDP connections badly. Since you are using VPN tunneling, you should probably avoid TCP over TCP scenario: if the VPN connection is using TCP, then I would rather use UDP for remote desktop connection. I would aim for UDP over UDP, but in a situation where the router can't handle UDP properly you could try TCP over UDP (that is VPN: TCP, VNC: UDP). You could also try to tune mtu size in tincvpn config.

Did you use WiFi? An old Wifi router can easily add half a second of latency. Even high end Wifi endpoint still adds a few ms of latency which can be significant considering that short distances (20 miles) of fiber has sub ms latency. A software router or switch can also add up to a ms of latency. Could also try SSH (tunnel) instead of VPN as SSH encryption might be faster.

I don't know what the Vultr instance uses but i had cable connection on both of my devices (home server and local machine).

I suspected ssh over tinc might bring latency since there is an extra layer of encryption, i will try ssh tunneling. Thanks!