Ok, we at at a point where the OP, 'nockieboy' has enough info to make a decision:
A: project must not have BGA, or it can have BGA.
If it cant have BGA, the OP must select to either go with a low cost older FPGA with DRAM, or an all in 1 IC solution like the MAX10 144pin QFP.
When using the older FPGA and DRAM, the op must contend with a more complex PCB, multiple power supply voltages, ram chips and bootprom.
B: Price sensitivity. If 1 BGA IC is allowed, the Lattice 16$ for 1 chip IC with almost 2 megabit internally pretty much kills everything else in logic density and memory. Lattice being the third largest FPGA vendor still has relatively decent toolset. However, you would still need a bootprom and a second regulator for the VCC core voltage.
C: design complexitity.
The TFP410 DVI Transmitter solves the headache of creating and testing his own DVI output serializer core (I realize that home made verilog examples of such a core already exist, but this can be extra work).
Now, with the video modes mentioned, anything he chooses will work, it the development effort and needed and if there will be room for special treats.
If I want a tiny PCB, 1 main IC and HDMI plug, the MAX10 eliminates a lot of complexity and may be possible to be done on a 5$ for 10x 2 layer PCB***. (You really need to know what you are doing and basically the bottom layer is basically a flood-fill GND with a few short trace jumps)
I would make this board a stand alone with a connector for the 8bit MCU board. I would also offer to make the IC's onboard ram useable as the 8bit cpu's system memory.
If the op went with the larger 2mbit Lattice part, he has the density and speed to offer something like 12 new 256 color sprites, any width up to the width of the screen, with a translucent colors, on every new line of video, from anywhere within the block of system memory, in real time without any overhead. With the max 10, he could get away with something like 8 sprites at the 180/or/160x240 mode.
For such a project, I would personally recommend using the standard SMPTE 480p base mode of 720x480, 16:9, 27Mhz reference clock as it will work on any PC monitor as well as any TV sold today. If the op wants 640x480, just center crop the image. (make a black bar an the left and right of the image.) Also, this standard mode makes integrating the standard HDMI embedded 48Khz stereo audio easy as the exact standard specs are well defined. Using the 25Mhz VGA 640x480 will add an obstacle upgrade path for embedded audio in the future.
This project is nothing more than a large number of start and stop sequence counters, driving another set of counters look-up memory, use the contents to look up more memory to point to alternate contents of same chunk of memory, and shift the right final content to a palette memory then to feed the DVI transmitter, or feed the internal DVI serializer.
This is why I said in an earlier post, run the internal display memory at 16x the speed of the output pixel feed, you you can read and use each read address to point to another place in ram, 15 times before creating your final resulting pixel. You may want to make your video memory 16 bits wide so you can access 16 bit words each time allowing a 16bit palette to be stored withing system memory instead of special dedicated registers or memory block.