Welcome to StackExchange, Patrick!
The tricky thing about what you're trying to do is that it'sIt's really difficult to cut off all avenues for creating an opportunity. If someone were to use DataLoader, or Salesforce for Outlook, or etc, they could create an opp without hitting any of the roadblocks!
I'd go back to the business and question the assumption: Do they really need to prevent opportunities from being created without a contact? Would it be good enough (or better) to prevent opportunities from moving past a certain stage without a contact assigned? An argument in favor of the latter: If a sales rep wanted to open an opportunity but didn't have the best contact's info, the rep might create a bogus contact just to get things going. The current business requirement is encouraging that.
If you can go with preventing the opp from moving past a given stage without a contact role assigned, then you can use a before update trigger (or a visual flow) to enforce the rule. Here's one example: