OP here. On a hunch, even though my package is in a PUBLIC GitHub repo, I decided to log in to shinyapps.io and entered GitHub access credentials as if it were a private repo, as described here. This allowed the package build to work during Shiny app deployment.
I don't know if this would have happened with any public GitHub repo (because all other packages my Shiny app uses are on CRAN), but maybe it's a bug with accessing a public GitHub repo that you are also the owner of?
It is possible that shinyapps.io uses the GItHub API to download packages from GitHub, and gets rate-limited. In which case adding your token is the right solution indeed.
If this is indeed what's happening, if there is any way for RStudio to detect the specific failure cause, a more informative error message would be great.
We've identified an issue with installing GitHub packages on shinyapps.io. We're working on a fix and hope to resolve the issue soon. In the meantime, I can confirm that enabling GitHub Private Repo Access is a temporary workaround.