I picture having an "uninstall" link beside the activate / deactivate links in the plugins panel. When clicked, a call is made first to a special uninstall action which may or may not exist, depending on the plugin. Then the plugin itself is deactivated, and then the actual plugin files are deleted.
A developer who writes a plugin that either creates a database table or adds files outside the plugin space could write an uninstall method. Such a method could be added to a special action hook that only runs when that particular plugin gets uninstalled from the admin panel.
This way, the user can uninstall a plugin without going through their ftp server or following an author's special instructions.
It makes things easier on developers as well, since they can spend less time worrying about what will happen if a user decides to stop using their plugin. Simply writing an uninstall method with no GUI or step-by-step documentation to worry about is really pretty easy.