I'm leaning towards SDRAM because you can get 32MBit chips for a few dollars. Looking at my notes, an 8 bit SDRAM part requires 30 pins on the FPGA which would only leave 21 bidirectional pins with the FPGA chip we are using now. So we will probably need to move to a chip with more available I/O pins to make it work.
Our intention is to add memory in a future revision, for now we want to get it into a working product with the 6K of BRAM that we can squeeze out of the S3E-250 chip.