Have you checked out Apollo Client? It's an alternative to Relay that works with all GraphQL servers and brings in a lot of the simplicity of Falcor: http://dev.apollodata.com/
It includes features like optimistic UI, easy ways to invalidate cache after mutations, arbitrary pagination models, and more.
I haven't. Maybe I will some time. My conclusion after struggling with Relay, though, was that there's a lot of complexity in GraphQL that I don't understand as well.
I'm 100% with you on Relay being overcomplicated. My first project with it involved a lot of set up and the other frontend developer completely gave up on learning Relay entirely.
In contrast, for a newer project I used Apollo and was up and running in no time at all. It's very easy to reason about, but also gives you great React integrations.
Yeah I don't think there is a clear story about how to put together a GraphQL server yet. It's not inherently complex but the content isn't there yet. It's something we want to target soon.
It includes features like optimistic UI, easy ways to invalidate cache after mutations, arbitrary pagination models, and more.
(Disclaimer: I work on Apollo)