10
Don't use threads, use an event loop.
The PIC18 is a small processor and an event loop based style means you don't have to keep many deep stacks hanging around. You need to write your code in terms of the event loop, but that is probably reasonable.
If you do have some long running tasks, use timers are different interrupt priority levels to allow higher priority event loops to preempt lower priority event loops, and put appropriate types of work into the appropriate event queue.
You can put an RTOS on there (there's an unofficial ucOS port, or you could check out FreeRTOS's PIC18 port).
Otherwise, you could try implementing coroutines in C by using setjmp and longjmp.