If someone loses their phone and needs Duo account recovery, their administrators can send them a reactivation link or make a self-service portal available where users can re-enroll devices themselves.
Typically when you enable 2FA on third-party sites you're provided with some backup codes to securely store in case recovery is needed. If someone were to lose their phone AND their offline backup codes, then yes, life can get difficult. To that end some people may choose to continue using a preferred app for third-party accounts that allow operations like sync across devices or backup and restore to any device, and use Duo Mobile just for Duo-protected applications.
In the scenario you describe it sounds like your users may already be using other passcode apps with some sync or backup/restore feature for third-party services, and just want to know if Duo's service requires installing the Duo Mobile app (too), which it does.