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:
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)
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)
Install the Company Portal, before launching it enable Exploit Protection and set it as a device admin.
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.
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.
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.