
Run Flows is a permission to allow users to run flows in Salesforce. For a long time, it was possible to give this permission through profiles and permission sets. However, in Spring '23 release, Salesforce removed this permission from the Guest User profile in all orgs. Since it is not possible to assign permission sets to guest users, it is not possible to give this permission through permission sets either. To allow guest users access your flows, you need to grant individual access to each flow that you want them to access.

Here is how to allow guest users access to flows.
Giving Permission to Guest User Profile
Go to flows in setup, find the screen flow, and from the actions dropdown next to the flow, select Edit Access. Select "Override default behavior and restrict access to enabled profiles or permission sets." and then choose the profiles that can use this flow. However, you won't be able to see the guest user profile here.

Go to the Experience Builder of your site and click settings. Select "Guest users can see and interact with the site without logging in" and then click the name of the profile. For instance, "Survey Profile".

Scroll down to the Enabled Flow Access and add your flow to the list. This will grant access to the selected flows.

Read this post to see how to create a public survey using screen flow.
Here is a link of a public Experience site with a screen flow. Since it is public, guest users (anyone) can run it. Go ahead and play with it!
Fantastic! After nearly pulling all my hair out as a new-ish admin-in-training this solution did the trick! Thank you!
Thanks much! I never would have figured out that I needed to go into Experience Builder to override default behavior before I would see the flow in the list of flows to enable. That must have taken a bunch of trial and error.
You are welcome, I am glad that you found it useful!