How can I programmatically create a media object and a new file and associate the file with the media object?
Ah, I always figure it out after I say I can't do it.  Once I specified the document type, it worked: 

$media_arr = [
  'bundle' =&gt; 'file',
  'langcode' =&gt; 'en',
  'uid' =&gt; \Drupal::currentUser()-&gt;id(),
  'created' =&gt; date('U'),
  'changed' =&gt; date('U'),      
  'moderation_state' =&gt; 'published',
  'field_file_document_type' =&gt; 1409, //1409 is the id for pdf
  'field_media_file' =&gt; [
    'target_id' =&gt; $file-&gt;id(),
  ],
];


Edit: I should mention that 1409 is the id we use for pdfs, yours will be different.  The field_file_document_type just needed to have a value in it to work.