It's not startups you should be worried about as finding data for them is difficult unless they already have a widely used product, use open data or have a partner.
The real ones to be worried about are the usual 'do no evil' suspects. They already have all the data.
Google will have no problem complying with this request. They already have the systems in place to do so without much effort. Many people have already requested data from Google.
Small companies dealing with their first request likely have (at best) a manual process that will take many hours of someone's time to process.
Whilst their processes might be superior (although that's debatable), they very much aren't up to speed with GDPR https://www.bbc.co.uk/news/technology-46944696 (even if the fine is small fry to them and it's financially more attractive to flaunt the rules)
That's a completely different issue from their ability to respond to data requests like the one linked. I'd assume the incremental cost for Google to send you the data it has on you is close to zero.
The real ones to be worried about are the usual 'do no evil' suspects. They already have all the data.