I have an Arduino UNO and DruinOS, which is derived from FreeRTOS, running happily on it.
FreeRTOS is a real RTOS and supports 8 bit microcontrollers like 8051, AVR, PIC18. I just ported it to a 18lf45k22 just because people were telling me that this is not possible
It certainly adds a few percent of overhead for those little machines, but I'm more after the concept of programming in threads compared to the superloop, as it is typical for the Arduino.
Projects are usually growing and having an RTOS just helps to break things into tasks and to add new tasks without seriously affecting the timing.
Hey I'm a geek and use a RTOS even on small microcontrollers
... but as bigger microcontrollers are getting cheaper and cheaper it's certainly a topic we should look into a bit to be ready to roll on future Arduino boards ...