Der xtightvncviewer passt die Kompression nicht automatisch der Verbindungsqualität an. Diese Parameter halte ich bei langsamen Verbindungen für akzeptabel:

xtightvncviewer -quality 2 -compresslevel 9 -encodings "tight hextile corre copyrect" localhost:5900