As for alternative terminals, rxvt-unicode-256color (actual name of the package) is a nice starting point (you can customize it via ~/.Xdefaults).Another good alternative and more close to what I think you are used to is lxterminal, the terminal emulator from Xfce.
Then you have Konsole (KDE's terminal) and GNOME's gnome-terminal, E17's fancy term, aterm, eterm, xterm...
And finally you have Terminator - albeit I'm not sure if it's a terminal emulator by its own or it needs gnome-terminal as an underlying base.
In any case tmux+{your terminal of choice} should be a better choice.