Lo principal es actuar en el orden correcto, porque una SIM-card en manos de un desconocido es más peligrosa que el teléfono en sí 🚨 Si pierdes tiempo con el correo y mientras tanto ese tipo recibe un SMS con el código de recuperación, listo, tendrá acceso a todas tus cuentas. Por eso primero llamas al proveedor, después al banco, y después ya te ocupas de los servicios en la nube. La SIM-card se puede bloquear en un minuto por teléfono.
Cuando arregles lo del proveedor y la tarjeta, tienes que entrar a Google/Apple desde otro dispositivo o computadora, ahí hay historial de inicios de sesión y sesiones activas. Mira si alguien más intentó entrar desde otro lado, y cierra todas las sesiones excepto las tuyas. Al mismo tiempo cambia la contraseña del correo, eso es la base para recuperar todo lo demás 💪
Después no te olvides de las redes sociales y los mensajeros, ahí generalmente puedes ver las sesiones activas y cerrarlas de forma remota. Y un consejo más: cuando consigas un teléfono nuevo, activa la autenticación de dos factores en todos lados donde puedas, y no solo por SMS, sino a través de una app generadora de códigos (como Google Authenticator), eso te protegerá de situaciones así en el futuro.