I found this out a couple of months ago: It *is* possible to uninstall programs in Linux, properly...if you use the Debian package management at least :)
So that means Debian and Ubuntu are good to go :)

Normally to remove a package you do this:

dpkg --remove package
or
dpkg --purge package
or
apt-get remove package

I usually use purge because it gets rid of the config files too :)
If you use apt-get remove though, you can then do this:

apt-get autoremove

And it will get rid of any libraries that are not in use by any packages. So if you install a package, and it ocmes with a bunch of libraries that nothing else uses, and you then uninstall that program...then autoremove gets rid of all those libraries too :)

Kind of like the old deborphan program...but built into apt :)

Neat huh?