VGA Output from Arduino
This is quite difficult to do well but there are a couple of examples. The main difficulty is in the speed of the CPU.

Here's one doing direct VGA output: Make: Arduino VGA Demo

If you Google "Arduino VGA" there are a few demo projects.

A couple options are the "TellyMate" shield that lets you output Composite rather than VGA (the single yellow connector you find on your TV. 

Another is the "PICASO Universal Base Board" and "PICASO VGA/SVGA Graphics Controller" - this is not a direct shield but probably the best option I have seen.

Both the above items are available from Sparkfun and Little Bird Electronics among other places.