On uninstall, does it make more sense to remove or remove completely?
 

I mean packages, not the OS

It depends on whether you think you might reinstall the package at a future date and therefore want to keep the configuration files.

Personally, however, I always remove the package completely:

sudo apt-get --purge autoremove packagename

This removes the package, its configuration files, and any dependent packages that are no longer used by any other packages.

If you want to go the whole hog, you can also remove the user-specific configuration files/directories which you normally find in (often hidden) subdirectories in your home directory e.g. /home/hydrurga/.Skype/ for the Skype package.

Agreed. If you're uninstalling to test something, then I keep configs, otherwise I always use purge.

Is apt-get --purge autoremove packagename the same as complete removal within the package manager?

If you're talking about Synaptic, no. Complete removal doesn't autoremove the unused dependencies, so is more the equivalent of:

sudo apt-get purge packagename

Does an apt-get autoremove do the trick as well? (Without package name, just "apt-get autoremove")

Yes. autoremove (whether used as apt-get autoremove or as the --autoremove option) removes all unused dependencies.