How are the packages vim-gtk and vim-gnome different from each other? I've tried both and the resulting Gvim feels the same (to me). If there is no difference, why are both packages maintained?
Both packages provide the same application, but compiled with different dependencies (e.g. vim-gnome depends on libgnome2). Vim-gtk is important only to people who use Kubuntu (or some lightweight desktop environment) and don't want to install GNOME libraries. If you use the standard Ubuntu desktop, the dependencies are already present, and you can safely use vim-gnome. I agree that it could be confusing.
If you run the command
sudo apt-get install vim-gtk
it will tell you how much needs to be downloaded. You can then abort the install at the confirmation prompt and do the same with gnome:
sudo apt-get install vim-gnome
and then accept or abort and go back to gtk.
If you're trying to install the minimum size, that may help you decide. However, if you choose gtk to save a bit of space and then later install something that loads the gnome libraries, you won't actually have saved anything in the long run.