This guy has done unbelievable things with low end PIC and also a color video game with multi channel sound and VGA output on a PIC18F2550!
http://pic24.ru/doku.php/en/osa/articles/vga_game

Using an RTOS...

Ioannis