The installer/uninstaller package I really like, although it may be too limited for your needs, is AGENTIX. It adds just 37kb to the package, and I am very happy with the feature set and ease of setting it up. It's very streamlined and quick to open and close. I find it is not buggy, flaky, and massive bloatware like InstallShield tends to be.
If you want a more powerful but still lightweight installer, consider the Nullsoft Installer. It is open source and has a ton of functionality and a full scripting language. It's easy to add pages like requesting and verifying a serial number during the installation, and easy to do different languages.
There are a lot of example code on how to use Nullsoft, even how to interact with REBOL.
One idea is to put a small cleanup batch file inside the User Profile folder and set that batch file to run, deleting all the other files in that folder, and then itself. You can tell Windows to run that script if someone clicks remove in "Add/Remove Programs".
This seemed useful:
http://nsis.sourceforge.net/Add_unin...emove_Programs