We looked at building a two-way sync tool in Google sheets to test out an MVP instead of building some custom tool and it was a shitshow from a data synchronization standpoint figuring out how to keep the state of each in sync is very hard. We abandoned the idea pretty quickly.

For problem (2), I'm not sure if you're directly returning data from lambda or if you're using lambda to use the sheets API to update the sheet after the data is returned.

If it's the first one, there's no way around it since lambda functions called through API Gateway have the 30 second timeout that you're running into. If it's the second you should be able to use two lambdas one as one that ingests the requests and adds it to a queue, and the second one (which can have up to a 15 minute timeout) that consumes the queue.