This is detailed in the following article:
https://developer.salesforce.com/docs/atlas.en-us.appExchangeInstallGuide.meta/appExchangeInstallGuide/appexchange_install_installation.htm
Install for Admins Only
Specifies the following settings on the installing administrator’s profile and any profile with the "Customize Application" permission.
- Object permissions—“Read,” “Create,” “Edit,” “Delete,” “View All,” and “Modify All” enabled
- Field-level security—set to visible and editable for all fields
- Apex classes—enabled
- Visualforce pages—enabled
- App settings—enabled
- Tab settings—determined by the package creator
- Page layout settings—determined by the package creator
- Record Type settings—determined by the package creator
After installation, if you have Enterprise, Performance, Unlimited, or Developer Edition, set the appropriate user and object permissions on custom profiles as needed.
Install for All Users
Specifies the following settings on all internal custom profiles.
- Object permissions—“Read,” “Create,” “Edit,” and “Delete” enabled
- Field-level security—set to visible and editable for all fields
- Apex classes—enabled
- Visualforce pages—enabled
- App settings—enabled
- Tab settings—determined by the package creator
- Page layout settings—determined by the package creator
- Record Type settings—determined by the package creator
- Note: The Customer Portal User, Customer Portal Manager, High Volume Customer Portal, Authenticated Website, Partner User, and standard profiles receive no access.
Install for Specific Profiles...
Enables you to choose the usage access for all custom profiles in your organization. You can set each profile to have full access or no access for the new package and all its components.
- Full Access—Specifies the following settings for each profile.
- Object permissions—“Read,” “Create,” “Edit,” “Delete,” “View All,” and “Modify All” enabled
- Field-level security—set to visible and editable for all fields
- Apex classes—enabled
- Visualforce pages—enabled
- App settings—enabled
- Tab settings—determined by the package creator
- Page layout settings—determined by the package creator
- Record Type settings—determined by the package creator
- No Access—Specifies the same settings as Full Access, except all object permissions are disabled.
You might see other options if the publisher has included settings for custom profiles. You can incorporate the settings of the publisher’s custom profiles into your profiles without affecting your settings. Choose the name of the profile settings in the drop-down list next to the profile that you need to apply them to. The current settings in that profile remain intact.
Alternatively, click Set All next to an access level to give this setting to all user profiles.
The Permission Set Groups Considerations and Permission Set Group Status and Recalculation documents are helpful here.
Permission Set Groups are calculated into an aggregate form, thus improving performance. In other words, they are processed at configuration/deployment time, and then reused. Having many Permission Sets may have some impact, but this impact is limited because of Salesforce Features and Edition Allocations.
Specifically, orgs are limited to at most 1,500 global Permission Sets and 1,000 global Permission Set Groups, with each group having a maximum of 100 Permission Sets. Of those limits, your org is only allowed to create 1,000 Permission Sets and 800 Permission Set Groups; installed packages can also have Permission Sets and Permission Set Groups, and installation will fail if the global limits are exceeded.
Whenever we see limits like this, we know that there is some impact to performance, even though it may not be explicitly called out in any document. These limits are in place to keep Salesforce running at an appropriate level of service.
So, in one sense, you don't need to worry about a significant impact, because there are limits in place to keep the system reasonably responsive. On the other hand, this information should inform your design decisions about how granular your Permission Set and Permission Set Groups need to be.
You can't just create one Permission Set per User or per field, for example. As long as your Permission Sets and Permission Set Groups are reasonably designed to fit within the limits from above, you should find minimal impact to your organization's performance.
So, presuming you're a typical organization, and you have a reasonable number of features and groups, your general implementation that you've described sounds like a reasonable solution in most cases.
Best Answer
It can't be done. I've had the same problem, your best bet is to start a new managed package.
However, if your App is uploaded to the AppExchange, and your a partner, you can try to contact Salesforce partner support (if your a partner and it is distributed on the AppExchange). Ask them to 'unlock' your package, you will have to have it uninstalled from all orgs where it has been installed.
PS. Oddly enough our package installed into edition that would otherwise not support permission sets, but than it wouldn't uninstall. "Uninstall Button" just disappeared and than it hung after you hit uninstall and never completely uninstalled.