All of these suggestions seem to make a pretty big assumption - that user stories can be prioritized at all without estimations. I've never worked in an environment where that is possible - maybe huge companies who have tons of money to burn. To me, it seems like the quickest way to burn through VC money... trying to build the most important / impossible things first without also building some low-hanging fruit that can help trickle in some money.
We use the following method:
Estimate what you know
Refuse to estimate what you don't and call it a spike
Tell management that at least 1 spike must be performed. The outcome / deliverable of a spike is either an estimation for the story (or stories) the spike was created for or some sort of email, document, powerpoint, etc indicating the lessons learned and the suggested next steps for the next spike.
After 2, 3, or more spikes for a business requirement, it quickly becomes apparent to the entire team and management that this is a risky area full of uncertainty. And, since management doesn't like things that don't have estimates, they tend to prioritize spikes... they want their estimates. Either way, it works out well - all of the high-risk and uncertain stories start bubbling to the beginning of the release and so everyone gets a much clearer picture early on about what is realistic and what isn't.
Even better, leadership learns quickly that spikes are not commitments since they are not estimated and our teams don't commit to things that aren't estimated.
The final step - a critical path for various components of the application (UI, Database, Services, etc)... this means spikes and stories. I know this may seem waterfallish and you don't need to do a full systems engineering critical path, but just a quick "this prevents or blocks this from being worked on". You need to quickly identify what can be done in parallel, what is blocked, etc. This really helps define release plans, sprint themes, and milestones.