I understand the whole catch-22 of creation, but as it turns out these relationships are critical to a ton of workflows, data tags and reporting.
Sounds like this might need to be something of a pop-up / wizard flow? Start to create deal and a shell of a deal record is created, search for and associate a company and/or contact, hit finish and the deal record is off to a good start.
Could also just have a designated stage upon creation where it’s okay to not have anything associated, but then absolutely lock it down from leaving this initial stage until users associate it to a contact and/or company. - I’m trying to do this via workflow, but there are too many gaps to really enforce it right now.