start with a cooperative task scheduler, single-stack. Some for AVR micros can be found on avrfreaks.net’s projects section.
There are many examples of these, with public domain source code. These are also called run-to-completion tasks, typically as a state machine, called repeatedly by a scheduler. They can be event driven.
C++ rather than C, is thought by many to be a poor choice for small memory microprocessors. Arduino’s environment uses C++ with GCC. If done carefully, it can be done. Be sure that you are totally C competent and with interrupt handlers before worrying with C++.
Next step up is an ARM7 or ARM Cortex M3 such as the LPC1768. The mbed is such a chip. You can roll your own or use their C++ libraries. You can use GCC for the ARMs with C++ as an option, or the 32KB limited size version of the excellent compilers from Keil and IAR (I prefer the latter).
In either case, the use of new() needs to be minimized or avoided, and try/catch is out of the question in small RAM micros.
And note too that developers for small RAM micros tend to use no scheduler, or a cooperative task non-preemptive scheduler, single-stack, and multiple state machines, rather than a classic RTOS.