I dual-boot Ubuntu 9.10 and Windows XP. In Ubuntu, most application uninstall in 0-10 seconds. In Windows, it can take up to an hour (rare, but times of ~15 minutes are fairly common). What is Windows doing that takes so long?
Not all uninstallers are slow. The uninstallers that are particularly slow are the ones that create a system restore point (mainly .msi), which takes a fairly long time. Installers that access the registry a lot are also a bit slower as the database isn't all that great.
Uninstallers that simply unlink files are typically very fast on the other hand.
In Ubuntu, uninstallers don't make system restore points or access a registry for settings. Most settings are contained in flat files which are simply unlinked.
Edit: In case anyone is unfamiliar with the term "unlink", it is what actually happens when you "delete" a file.
A good description is found in the unlink Linux man page:
This is why recovery programs can find files you deleted a long time ago. If the space that was marked as "available for reuse" hasn't been overwritten, the data can easily be re-obtained.