Freerdp does not require any gui. It is a direct descendent of rdesktop (that probably is used by that "Terminal Services Client").
It does work great with NLA.
Make sure you read up on the hows and whys on the site if you want to share folders/audio/printers with the server - this is a bit convoluted by using virtual channel plugins but it works (i even printed via RDP to the printer connected to my Debian box from a Win2008 server). It even works with RemoteApp (but there you have to do a bit of configuring on the Win2008 server).
For basic usage, no extra complications are necessary.
If you have issues connecting to NLA servers, check the ~/.freerdp/known_hosts file, in some cases (same ip/hostname, multiple rdp servers behind it) this is the cause of issues. Just delete it or edit it and delete the troublemaker lines.
This is freerdp on Debian (it is in the repos there as freerdp-x11):
$ xfreerdp --help
FreeRDP - A Free Remote Desktop Protocol Client
See http://www.freerdp.com for more information
Usage: xfreerdp [options] server:port
-0: connect to console session
-a: set color depth in bit, default is 16
-c: initial working directory
-D: hide window decorations
-T: window title
-f: fullscreen mode
-g: set geometry, using format WxH or X% or 'workarea', default is 1024x768
-h: print this help
-k: set keyboard layout ID
-K: do not interfere with window manager bindings
-m: don't send mouse motion events
-o: console audio
-s: set startup-shell
-t: alternative port number, default is 3389
-x: performance flags (m[odem], b[roadband] or l[an])
-X: embed into another window with a given XID.
-z: enable compression
--app: RemoteApp connection. This implies -g workarea
--ext: load an extension
--no-auth: disable authentication
--no-fastpath: disable fast-path
--gdi: graphics rendering (hw, sw)
--no-osb: disable offscreen bitmaps
--no-bmp-cache: disable bitmap cache
--plugin: load a virtual channel plugin
--rfx: enable RemoteFX
--rfx-mode: RemoteFX operational flags (v[ideo], i[mage]), default is video
--nsc: enable NSCodec (experimental)
--disable-wallpaper: disables wallpaper
--composition: enable desktop composition
--disable-full-window-drag: disables full window drag
--disable-menu-animations: disables menu animations
--disable-theming: disables theming
--no-rdp: disable Standard RDP encryption
--no-tls: disable TLS encryption
--no-nla: disable network level authentication
--ntlm: force NTLM authentication protocol version (1 or 2)
--ignore-certificate: ignore verification of logon certificate
--sec: force protocol security (rdp, tls or nla)
--secure-checksum: use salted checksums with Standard RDP encryption
--version: print version information
Although freerdp does not require a GUI, it is included as a plugin (does not use the separate freerdp binary) in Remmina (along with VNC/NX, built in ssh tunneling, fullscreent toggle with popup menu at the top, allows profile creation and whatnot), which is a great GUI for remote administration. I use it daily for VNC/RDP adminitration and its really good. It is available in the Debian repositories.