As Michael said, the ATMega328 is has limited SRAM (2K) and processor speed (16 MHz).
I found that using PROGMEM for as much as possible is essential (see: http://www.arduino.cc/en/Reference/PROGMEM
if you are not already familiar).
The TVOut library has some very nice features, however I have found that you have to extend at least a few to work well with bitmap graphics games. I am sure the same is true with vector-based games.
Due to how TVOut works, you have to use polling serial for debugging instead of the others that are normally used in the Arduino IDE (if you plan on debugging that way).
As far as adding a processor/co-processor I know that the Gameduino project already adds an FPGA as a graphics co-processor to an Arduino-based project, so it would work for a lot of ATMega chips.http://excamera.com/sphinx/gameduino/
There are also other projects that add other chips (like the Parallax Propeller MCU) as a "graphics co-processor" for an Arduino/AVR (DigiStorm (not yet released), or Chameleon: http://www.xgamestation.com/view_product.php?id=51
Technically, it would even be possible to add another AVR as a graphics co-processor, or use an R2R ladder, or another chip like the AD725
See: Uzebox - http://belogic.com/uzebox/index.asp
Any of those options can be "trumped" with a nice little color LCD with an SPI interface, and have the added benefit of portability. Something like this works well: http://adafruit.com/products/684
There are plenty of others available as well.
To me though, as interesting as these options may be, it comes down to a philosophical question: Do I want to get the most that I can out of a single chip (for the challenge), or do I want to add hardware/glue logic to make a simple chip do something "big" (ie: running Linux, http://dmitry.co/index.php?p=./04.Thoug ... 0on%208bit
). Either are fun, it is just a matter of what you want to do. I go down the path of using minimal hardware to make something interesting.
For a nice balance between minimal hardware/software and ease of programming on an AVR-based platform, Hackvision is a great product! Other alternatives will lead you down the path of more complexity (either in hardware or software) for really not a significant benefit. What do you need to have a good game platform? Video (in one form or another), sound, and a controller (or other user input). You have all of that on the Hackvision in one product.
[Edit:] Lol! That totally sounds like marketing copy, but seriously, I mean it
Hopefully that helps.