There are quite a lot of microcontroller RTOSes[1] for the AVR platform, which means you can run them on the Arduino (although you'll need to use avr-gcc not the Arduino IDE for these.)

http://www.femtoos.org/

http://www.barello.net/avrx/

This one actually looks like it might use the Arduino IDE: http://code.google.com/p/duinos/

(Also: GIYF: 'RTOS AVR' and 'RTOS arduino')

[1] The hard part is separating anything that's a serious & maintained project from something someone developed once as a toy/interest project and never used for anything.

I've been writing one with my little brother: https://github.com/splicer/arduin_os

It still has a ways to go, but it's able to context-switch between threads. Feel free to fork it if you want to contribute.

It's an 8-bit RISC chip, so it might be a little small. It's more of a micro-controller than a CPU, if you know what I mean.

Agreed. Also, it really just is a micro-controller. From what I understand the internal ram and flash plus all the other special functions (SPI, UART, ADC) are what make a micro-controller a micro-controller while a MPU or CPU have data and addressing buses used to talk to external devices. Micro-controllers incorporate a bunch of common functions into them that a CPU or MPU would need to talk to an external device for (while micro-controllers tend to lack said external buses).

really? i was under the impression it was a really fast 8051 clone.

The AVR is RISC, it's not a 8051 clone at all. See <http://en.wikipedia.org/wiki/Atmel_AVR>.