Currently on Digikey, the largest cheapest parallel EEPROM is 1M×8 for $2.74 (MX29F800CBTI-70G or MX29F800CTTI-70G). The cost of the boot ROM (smallest 5V parallel ROM we can find) is 64K×8 for $1.24 (AT49F512-90VC).
As soon as you give up on sticking with the NES's ancient memory bus, everything gets kinda awful:
To interface with any kind of serial and most NAND FLASH, you'll need some kind of PAL; Mouser seems to have the cheapest 16V8 at 55¢/1. Serial load speeds on the NES are going to be lousy without a hardware assist (see also joypad reads), so unless you throw enough CPLD/FPGA at the problem, using some kind of parallel flash is greatly desirable. (e.g. Compact Flash, 3V parallel NAND FLASH, 8 SPI EEPROMs ganged up in parallel) 1bit serial read speed results will be comparable to the FDS, so not terrible but nothing I'd be proud of.
Large-banked parallel-accessed NAND FLASH that isn't CompactFlash isn't available in 5V, but it at least has enough fewer lines (17) that a 5V↔3V logic converter is reasonable. (e.g. the MT29F16G08CBACAWP, a 3V 1G×8x2 for $6.59)
Coprocessors to load data into CHR are fine once you spend enough money on a CPLD.
So, to break it down:
A giant BNROM-like game will cost $1.2 for the CHR RAM, 20¢ for the banking logic, and $2.7 for the ROM ($4/1MB, $7/2MB, $10/3MB or so); larger than that will cost 30¢ more and $2.7 per megabyte
A giant FDS-like game will cost $1.24 for the boot rom, $2.4 for two RAMs, 55¢ for the glue logic, 50¢ for voltage regulator and conversion, and 45¢ per 1MB SPI EEPROM (digikey, W25Q80BV): $5.3/1MB, $5.8/2MB, $6.3/3MB &c
A gargantuan FDS-like game will cost $1.24 for the boot rom, $2.4 for two RAMS, 55¢ for the glue logic, 50¢ for a socket, and $4-10 for any commercial flash format (CF, SD plus voltage regulator+shifting): $9…15/1,2,4GB
TL;DR:
- Less than 1MB of data: Don't bother trying with anything funny.
- More than 2MB but less than 9MB, consider 3V SPI EEPROMS.
- More than 9MB, consider SD.