Good choice of OS! Since there are so many great terminal emulators for Linux, I'll list the Gnome-Terminal options here; feel free to substitute equivalents in your term of choice.
If you want to play with the new NCurses interface:
160+ column terminal MUST be set BEFORE telnetting. (A bug in how dgamelaunch and ncurses interact prevents terminal-resize messages from being received)
For all interfaces' settings:
UTF-8 Default Encoding (!!!)
Allow bold text
Monospace font
Scrolling disabled
White-on-black default text
After all that, just `telnet nethack.csh.rit.edu` (or click this link).