Okay, so, this is probably very, very, late, so I don't know if it was a possible solution when you asked, but it does look like there's something now, for screen flows at least.

To explain the screenshot a bit:
- Create a screen flow, or open up the one you were tinkering with.
- Get whatever records you wanted to pull your choices from (I used leads for this example), wherever you like so long as it's before the screen you want to display these choices on. Remember to store "all records" instead of "the first one".
- Add or open the aforementioned screen element.
- Find the "picklist" component and add one to the screen, where you want it on the layout. Name it and so on.
- In the "enter value or search resources" space under "Choice" (that red-outlined bit on the screenshot), pick "New Choice Resource".
- Pick "Collection Choice Set". Note: you can also pick "Record Choice Set", which lets you do step 2 right there.
- Pick the field you want to generate your picklist values off of. In the screenshot, this is "City", so you'd get a bunch of choices like "Mumbai" or "Annapolis" as your resulting picklist values.