1. Update Composer to 2.x locally with composer self-update --2
2. Run composer update, which will fail for a couple of plugins, but will update craftcms/plugin-installer to 1.5.6
3. Delete the /vendor folder (you can do this with rm -rf vendor)
4. Run composer update (or composer install) again, as the lock file has already been updated in the first step, and craftcms/plugin-installer is locked to 1.5.6 now, so the plugins should install fine.
5. Commit & Deploy

The lock file is backward-compatible with 1.x, so the deployment will work on the server whether Composer has been updated to 2.x or not.