Writing new functions into progmem after main program is burned
First, I keep hearing that you can't write to progmem at runtime. But
  isn't that what a bootloader does?


Indeed. My understanding is that non-bootloader code cannot write to
the Flash, except on the smallest AVRs. You may need to check the
datasheet of your target MCU.


  Second, once a user program ends, I should return to the OS.


You could require for the user programs to be linked against a library
you provide. Just implement void exit(int status) in that library and
it will automatically override the version from avr-libc.