I'm using rdesktop (rdp) to connect to a windows machine, rdesktop is falling back to 16bit color (since it does not support 32bit).
It works quite well, the only issue I have so far (in 16bit, rdp or not) is that I get a black square instead of custom cursors (e.g. using HelloImage toy)