Whats the best way of going on to this.
Starting to learn how to program.
From before Christmas:http://arduino.cc/forum/index.php/topic,21441.0.html
Some numbers for you to play with:
From the VGA demo video you showed, assuming 320 x 200 resolution, the visible part of each line of video lasts (IIRC) about 25 microseconds (his timing was probably a bit lax, but the monitor would be a little forgiving).
That's enough to execute about 400 instructions (machine instructions, remember, not C statements) at 16MHz.
Most of those instructions will be writing stuff to the output DACs, leaving the blanking overhead of about 10-15% of the total frame time to do other stuff.
Is your programming up to it?