On the server I just install vim and scp -r .vim* to the server on the desktop I spend most of the time using emacs and only vim when I don't have emacs open and need to do a quick edit.
Tramp mode as stated is painfully slow and emacs doesn't really work for me in terminals as well as vim.
Probably only if you have a mouse connected to your computer. It is much easier for cutting/pasting between documents in different windows in a gui. I understand there are plugins for vi that work (I use vi most of the time), but it's easier for me to just use vim. Seems like to a first-order approximation gvim = vi + gui plugin
vim has to be built with X11 (gvim) support though b/c vim and gvim are really the same binary, IIRC (gvim = vim -g).
If you're an Emacs user, probably no particular advantage. I use GVim because as a GUI app it allows me to use my mouse for stuff like selecting areas and copy/pasting. I also like the workflow of having my file open for editing in a separate window and getting my shell prompt back straight away.
However, PuTTY only switches on XTerm mouse reporting when an app needs it, so it should be easy enough to bind ":set mouse=a"/":set mouse-=a" to a hot key, and toggle mouse support on and off depending on the required operation.
What kind of problems are you facing running emacs in terminal? I always run emacs in terminal (wrapped inside a screen session) and I have found no problem so far.
I run emacs-trunk/rxvt with 256 colors/bash. But have also used gnome-terminal.
I suggest trying zsh.