@Anonymous, we're very much in the same situation as you. What I've learned is that the concept of "Run Only Users" only applies to "manually triggered" Flows. In particular, this means Flows initiated using a "Flow Button", and NOT those with a "for selected items" trigger (even thought those are "manually triggered"). This severely limits the usefulness of Flow in our environment.
What has worked for us is adding SharePoint lists/libraries as owners. Doing this causes the Flow to "inherit" (for lack of a better term) the permissions of the list. Users with Edit permission or higher can edit the Flow; those with Contribute (the closest equivalent to read/write/execute permissions) can initiate or execute the Flow. However, even in this case, the Flow is using the author's Connections. So, actions taken are attributed to the author of the Flow. This is similar to how Impersonation Steps worked in SharePoint Designer 2010. In some situations, this is acceptable, and even advantageous, but obviously it's not always ideal.
The biggest issue we've run into using this method is that when emails are sent (and we have a LOT of workflows that send emails), they are sent as the Flow Author. However, we've worked around this by setting the "Send As" property to an O365 Group address or Shared Mailbox to which the Author has "Send As" permissions. If nothing else, this disassociates the individual user from the email.
I've submitted a suggestion (I don't recall where at the moment) that Flow Authors should be able to set an action to run as the Author or the user executing the Flow. I think that would be provide the best overall flexibility for most purposes.
