ben wrote:
  Remember this is the classic computer list so, being
about 10 years  
behind is normal
  around here. What can you recommend that has 5 volt
I/O, 
The last Xilinx FPGAs with 5V-tolerant I/O were the Spartan 2 family.
They still make those, but they are tiny and slow by today's standards,
and you have to use a really old version of the Xilinx software to
develop for them.
I don't think the situation with Altera is any better.
Some of the latest FPGAs (e.g., Virtex 6) don't even have 3.3V-tolerant I/O.
I'm pretty much resigned to using external level shifters or
QuickSwitch-style parts when I need to interface to 5V systems.
  nonvolatile memory and 
Most FPGAs don't have nonvolatile memory.  Certainly the mainstream ones
that have high logic density do not.  They use a separate serial flash
part to load the configuration at power-up.  (The Spartan 3AN includes
the serial flash part in the same package.)
  mid-sized number of FPGA macro cells. Something one
can use to  
emulate a PDP
  computer with up to 512Kb of memory. 
I'm not sure whether you mean 512 Kbits or KBytes.  There are a number
of FPGAs with 512 Kbits of dedicated blockram, but if there are any with
512 KBytes, they must cost a fortune.  You're generally much better off
with an external SRAM.