This may be a little pie-in-the-sky, but we have an idea to make a fully functional VGA interface for the Arduino.
We'd like to use a Microchip PIC microcontroller if possible as the core of it, and we have already had some success with a dsPIC33 chip.