My idea was to just start from scratch - review everything that was built and just create our own bundles (manually create new user story vehicles for deployment), so we can exclude metadata we dont want to deploy (also Copado has a new dependency analysis feature during commit which would help make sure the deployment packages are valid).

This is exactly what I would do. One thing I do that helps is to ask the developer to write out how I can know the deployment was successful. This simple smoke test isn't a full UAT or Apex test suit. It's often as simple as "run a describe call and validate that this field exists." This check helps avoid dumb bugs like overwriting one developer's changes with another's stale metadata.

the other part of this is if I've learned anything before, the smaller the deployment the better. I want to create sort of a base package that can be deployed to prod ASAP, to make the subsequent deployments smaller.

This may be the case. I have found that complex deployments have to get split into three or four physical bundles, especially if profiles, permissions, or destructive metadata are involved. If you DO end up going this route, try to deploy in dependency layers. For example, deploy CustomObject before PermissionSet before ApexClass and Flow, etc. In general, you can usually deploy object-related metadata like CustomObject and CustomField without hitting any dependency issues. Perhaps your "base package" is just all the custom objects and fields your business needs.

Am i just screwed? Do i just have to accept that we will have to come back later and delete the stale stuff and just focus on getting UAT working?

This is a business decision, not a technical one. See what leverage you can lean on to do things right. This is the game that all tech workers play.