If you add a library to the bound script, then the library setting will also be in the bound script attached to the copy of the Sheet.
If the user copies your Sheet, then the end result will be that the user will have a copy of the template Sheet, and that Sheet will have a script bound to it, and that bound script project will have the library already added to it.
So, your users will automatically be using the library, and the library file will always be the same.
Because the library file is always the same, then when that library file is verified by Google, the user won't see the warning message.
And the script bound to the Sheet is owned by them, so that doesn't need to be verified by Google.
A problem that people have with libraries, is how to update the users to a new version of the library.
But if you add the library to be used as the "head" version and not a numbered version then it will always be using the latest code.
Just don't do any development in the library file. Do your development in a different Apps Script file.
If you don't want to publish to the Google Workspace Marketplace as an add-on, then what I described above is your only other option.
You could ask your users to add the library themselves, but from how you describe your users, that's not an option.
So, the strategy that I described above avoids the need for the user to add the library themselves because when they copy
the Sheet, BOTH the bound script, and the library added to the bound script get transferred to the copied Sheet file.
I did a test with copying a Sheet file with a bound script that had a library added, and the library was added to the new bound script.
I don't use libraries, so I'm not sure if there is something important that I'm missing,
but I think that it might be worth it to you to try.
Test it yourself before you inform your users.