What exactly about being a startup makes this a lot harder? I'd expect a startup would in many cases have a fairly easy time answering requests like this, since it won't have built years worth of legacy systems, half-abandoned projects, weird cross-department data accesses etc that could catch a large company here. You'll likely have fairly centralized storage and a reasonable number of service providers you use for specific purposes. + the typical startup has more or less the same relationship with every customer, so it should be fairly easily repeatable once you've documented it once.
For the few small companies I've worked for, this would have been a bit of work once (document the dataflows), and then a fairly easy set of queries to be repeated each time.
It's not just about answering the questions. It's also about answering them in a legal-safe way that won't put you in more trouble than not answering them at all. And any small variation in the questions can require someone with legal experience just checking this, which costs money.
To add to a sibling comment, Google can afford a big enough legal department for estimated 0.00000x% of their turnover that deals exclusively with these.
For smaller organizations, this becomes more like 0.x% of turnover...
Not to mention the distraction and plain overhead when you're juggling so many other things.
Having fewer people. The task may only be 1/100 as hard for a startup as for Google, but there are 1/10,000 as many people to perform it. If so, the burden on the startup is 100x greater than on Google.
If you work with data security departments at large companies, you get these types of questionnaires all the time already. And every single question has been answered a dozen times before, but each new request's questions have subtle nuances such that it's impossible to build up a FAQ comprehensive enough that a non-technical person could copy-and-paste answers in a legally safe way. You'd think it would be possible, it just isn't.
The part that's not clear about the GDPR is whether you're obligated to manually answer any data-related question a user has, or if you can just post a comprehensive FAQ + data export / account deletion tool, and auto-respond to GDPR requests with links to those.
Looking this over, and looking at the startups I've either worked for or applied at, I really don't see how it would take more than a couple of hours to fill out the bulk of this form (the parts that would be reusable for every request after it), and then a couple of database queries for the specific data for the user.
For the few small companies I've worked for, this would have been a bit of work once (document the dataflows), and then a fairly easy set of queries to be repeated each time.