Option 1: Interpreted Languages
This doesn't directly answer the question (which is an excellent question, BTW, and I hope to learn from an answer which does address it directly), but it's very common when doing projects which can load external programs to write the external programs in an interpreted language. If resources are tight (which they will be on this processor, have you thought about using a PIC32 or small ARM processor for this?), it's common to restrict the language to a subset of the full specification. Even further down the chain are domain-specific languages that only do a few things.
For example, the elua project is an example of a low-resource (64 kB RAM) interpreted language. You can squeeze this down to 32k of RAM if you remove some features (Note: It won't work on your current processor, which is an 8-bit architecture. Using external RAM will probably be too slow for graphics). It provides a fast, flexible language in which new users could easily program games if you provide a minimal API. There is plenty of documentation available for the language online. There are other languages (like Forth and Basic) which you could use in a similar manner, but I think that Lua is the best option at the moment.
In a similar vein, you could create your own domain-specific language. You would have to provide a more full-fledged API and external documentation, but if the games were all similar then this wouldn't be too difficult.
In any case, the PIC18 is probably not the processor I'd use for something which involves custom programming/scripting and graphics. You may be familiar with this class of processors, but I'd suggest that this would be a good time to use something with a display driver and more memory.
Option 2: Just reprogram the whole thing
If, however, you're already planning on programming all the games yourself in C, then don't bother with loading just the game logic from the SD card. You have just 32kB of Flash to reprogram, and could easily get a 4 GB microSD card for this. (Note: larger cards are often SDHC, which is harder to interface with). Assuming that you use every last byte of your 32 kB, that leaves room on the SD card for 131,072 copies of your firmware with whatever game logic you need.
There are plenty of appnotes for writing bootloaders for PICs, like AN851. You'd need to design your bootloader to occupy a specific region of memory (probably the top of the memory region, you would specify this in the linker), and specify that the full firmware projects do not reach this region. The appnote spells this out in more detail. Just replace "Boot section of the PIC18F452" with "Boot section I specify in the linker" and it will all make sense.
Then, your bootloader just needs to allow the user to select a program to run from the SD card, and copy the whole thing over. A UI could be that the user has to hold down a push button to enter the selection mode. Ordinarily, the bootloader would just check the status of this button on reset, and, if it's not being held down, boot into the game. If it's held down, it would need to allow the user to choose a file on the SD card, copy the program over, and continue to boot into the [new] game.
This is my current recommendation.
Option 3: Deep magic involving storing only part of the hex file
The trouble with your envisioned mechanism is that the processor doesn't deal with APIs and function calls, it deals with numbers - addresses to which the instruction pointer can jump and expect there to be code which executes a function call according to an API spec. If you try to compile just a part of the program, the linker won't know what to do when you call
toggle_led(). You may know that those functions exist in the hex file on the processor, but it needs to know precisely which address they reside at.
The linker already breaks your code into multiple sections; you could theoretically break this into additional sections with some
#pragma incantations. I have never done this, and don't know how. Until the above two methods fail me (or someone posts an awesome answer here), I probably won't learn this mechanism, and so I can't teach it to you.