Thanks to the steps posted by @tetto and the commands shown by @imperfect I was able to get my work profile set up and running.

As I was playing around with the steps posted, I was able to solve the issue of work apps not showing up in your launcher. I don't remember for sure, but I think here are the steps I took:

1. In the owner profile, install any apps that you'll want to use in the work profile using Aurora or Play Store (I chose Aurora)

2. This is the key step. Install any apps that will be required by your work profile policies (I'll mention at the end how you can figure this out). This INCLUDES Google Play Services from the GrapheneOS App Store (Both GmsCompatConfig and Google Play Store). I'm not sure if you need to be logged in to the Google services. (I was, but you may not even need to launch the Play Store)

3. Install the Company Portal, before launching it enable Exploit Protection and set it as a device admin.

4. Follow the steps like you would on a normal Google device. You'll eventually get a screen that says "Let's set up your work profile." Hit "Accept & Continue", wait for the next screen that will want you to click "Next". Don't click next.

5. Here, connect your device to any machine where you can run ADB. In the ADB shell run pm list users and make a note of your work profile's user ID (10 in my case) then run the following commands:

   pm install-existing --user 10 app.grapheneos.gmscompat
   pm install-existing --user 10 app.grapheneos.gmscompat.lib
   pm install-existing --user 10 app.grapheneos.gmscompat.config
   pm install-existing --user 10 com.android.vending
   pm install-existing --user 10 com.google.android.gms

   Replace the user ID (10 in my case) with your work profile's user ID. You'll also want to run these commands for all the apps you installed in steps 1 and 2.

6. Now back in the Company Portal app, hit next and you should be able to proceed as if you're setting this up on a regular Google device. I had zero errors and everything went smoothly.

The key here is step 2. If you already set up a work profile on another device, it makes it really easy. Look at the apps that were installed by the Company Portal in your work profile and ensure you include them in step 2.

If not.. follow the guide @tetto posted and once you have your work profile running, open up the Play Store in the work profile. Your organization probably limited the number of apps allowed in the work profile. Make a note of all of them and just install them all in step 2. Once the work profile has been set up you can uninstall the ones you don't want.

You still will not be able to install any applications once the profile has been set up. I believe that will be resolved once these changes get merged: https://github.com/GrapheneOS/platform_frameworks_base/pull/147

This is all from memory since I didn't try to replicate my results. If you notice that I missed a step, please make a correction.

Success!

Shout out to @imperfect for his input! Thanks to that, my device now has Company Portal installed, work profile created, the device registered with Intune, and functioning work apps (Teams, etc). Most of the advice above and elsewhere online does not require the work profile or enrollment in Intune, which was my failure point.

Do this all from the owner profile. Do not use Shelter. Do not manually create a work profile. Do not create a separate Graphene user.

• Under the owner profile, install any apps you'll want to use in the work profile later on.
• Install Company Portal (Play Store, Aurora, etc)
• Before launching it, enable exploit protection and set it as a device admin app
• Now launch Company Portal and sign in
• 'Begin' company setup and 'Continue'
• "Setting up your work profile" transitions to a "Let's set up your work profile" screen. 'Accept & Continue' then it'll work for a minute, then prompt you to tap 'next', WAIT! Do not yet tap next and leave that screen open.
• Install apps to the work profile via ADB
  • I did not include gms items or android.vending as imperfect did since I install those differently below
  • pm install-existing --user 10 com.microsoft.office.outlook etc. 10 was my work profile ID as identified by pm list users
• Go back to the Company Portal app you previously left open and tap 'Next'
• It spins indefinitely. You'll know it's gone as far as it will go when the Company Portal app disappears from your app drawer (because it was moved to the work profile)
• Go to Settings > Apps > All Apps > 'Work Profile' tab
• Select 'App Store' (Graphene) and the launch icon in the top right to launch it under the work profile
• 'Google Play Services' Install (includes GmsCompatConfig, and Google Play Store dependencies)
  • Note that there appears to be a patch in the works for this Google Play requirement in the work profile: https://github.com/GrapheneOS/platform_frameworks_base/pull/147
• Reboot
• Go to Settings > Apps > All Apps > Work Profile tab, tap 'Company Portal', enable exploit mode, then the launch icon in the top right to launch it under the work profile
• Sign into company portal again.
• It initially hung on "Setting up your work profile" (red banner with company name up top), then eventually failed with something like "Unable to create work profile. Contact your company IT admin".
• Reboot
• Go to Settings > Apps > All Apps > Work Profile tab, tap 'Company Portal', then the launch icon in the top right to launch it under the work profile
• Sign into company portal again.
• Repeat. This time, the 'Create Work Profile' step was already checked. It immediately went to "registering" then "finishing setting up your work profile..." and completed!

I'm able to use apps (Teams, etc) that require the device be registered in Intune. The annoying part is that I can't launch them directly from the owner profile home screen or app drawer. You have to go to Settings > Apps > All Apps > 'Work Profile' tab and launch from there. I'll explore to see if I can create a shortcut for this or launching apps under the work profile.

I just achieved this about 10 minutes ago. We'll see what type of experience I have using work apps over the next week or so.