When is it appropriate to remove a plugin's settings? On deactivation or uninstall?
Remove data only on uninstall. Deactivating plugins can be done by mistake or in order to troubleshot some other problem and you don't want to make the plugin users to config everything again in this situation.
Think about your PC software, does it delete its data when it is being closed and become inactive? no, only when it is uninstalled. Same applies here.
Actually the uninstall option is relatively new and it was created specifically to have a point where you know it is safe to delete data.
That depends on when the data is created.
If you register and set the options, create the tables etc. required by your plugin during install, you should not remove it on deactivation - or else you wouldn't be able to use the plugin after re-activation.
If you register and set the options/create the tables etc. during activation, you're fine to remove it on deactivation.
However, why would you want to do that? Do you write that much to the database that the site is running faster with your plugin's data removed?