VGA interfacing with PIC
If it's not overkill for your application, you could add an ISA interface to your PIC and pick up an old video card somewhere.

However, supercat points out there's no PC to run the video BIOS, so probably this wouldn't work.

I did find a post on hackaday doing a similar thing with an AVR that might be good for inspiration.