I've seen discussion on Reddit that disabling shader caching might fix this issue. Also, maybe check your backup's sku.sis file to see if appids for redistributables were included in the backup? If it was, you may see success in making a backup with the build_installer command, which has the downside of redownloading the game but the upside of the backup depots being exactly what comes from Steam's servers rather than a recompression of your local files. (It's a niche feature, but uses the same format as a backup and any account that owns a game can do it. Documentation here. Just ignore the parts about using a "gold master" or other sdk files - the backup itself will work for your use case.)
Nothing extracted yet.
Your system information
tar -zcvf ~/Desktop/steam-logs.tar.gz ~/.steam/steam/logs]steam-logs.tar.gz
Please describe your issue in as much detail as possible:
When restoring a game backup on a fresh install (linux -> linux), steam tries to download the entire game before the games dependencies.
For example: counter strike 2 requires Steam Linux Runtime and Steamworks Common Redistributables.
When I restore the game: counter strike 2, Steam Linux Runtime and Steamworks Common Redistributables are added to my download queue, but counter strike 2 is downloaded first and the other two are in queue. I then cancel the restore. Counter Strike 2 is removed from downloads, but it's dependencies continue to install. I wait for the downloads to finish, then restore counter strike 2 again, and the game restores from the backup correctly.
Steps for reproducing this issue: