OK, I know what's happened now: formatting data and cache is equivalent to a factory reset, but system is where the ROM lives. So formatting system erases the phone's operating system, and that's why it goes straight to recovery.
So you need a new ROM. As you have a custom recovery, I'd be tempted to try installing a custom ROM rather than using an RUU. The best place to find ROMs is probably
XDA-developers. I can see a number of ROMs there which you could choose from. There's also a
guide thread there, the second post of which concerns flashing ROMs.
The general procedure is that you need to use fastboot to flash the boot image for the ROM, then flash the ROM (surprises me slightly - I'd have done it the other way round). So to install the kernel, download the boot.img you need (the right one for the ROM) and then:
fastboot flash boot boot.img
To install the ROM, copy to the SD card, go into CWM, do a factory reset (data and cache are enough) select the "install from card" option, select the ROM, install it. Then reboot the phone and you should be OK.
Don't worry if the first boot after installing a ROM is slower than usual, as it will have to rebuild the dalvik cache.
I'm afraid I can't recommend a particular ROM because I don't own a Desire C, so have never used any of these ROMs.