Rdesktop good
Well, the good folks at my CS dept have thankfully installed rdesktop on the Linux machines on campus, so a simple rdesktop -a 16 mylaptop worked :) (the -a 16 should be specified for Windows XP machines, otherwise everything looks ugly and works slower).
The source of my happiness is here: http://www.rdesktop.org/.