What type of memory allows for most parallel read/write operations per clock cycle in an FPGA

Here's how I'd do it...

I would start with a Xilinx Spartan-6 FPGA. The reason I'd go with this is because they have "hard cores" for a DDR-SDRAM interface. By hard core, I mean that the circuitry for this memory interface is a dedicated chunk of logic and not in the normal "user programmed fabric of logic". This means that you're going to meet timing, and you don't have to write this logic on your own.

Next, I'd hook up some DDR2 SDRAM to the part. DDR2 SDRAM is fairly inexpensive, easy to get, and certainly fast and large enough for what you want to do. I'd start with a 16-bit wide data bus, and increase that if you need more speed. You can use the Xilinx CoreGen or Memory Interface Generator to get your DDR2 interface core.

The rest is "relatively easy", in that it's just moving data around and generating the proper sync pulses.

One major down-side to this approach is that you're basically limited to using BGA's for both the memory and FPGA. One plus side is that there are FPGA development boards that already have this circuitry on it.

I got this working, with one specific change although to be honest some other edits may have helped too.

I thought about how drive_data is set up using combinatorial logic, but the outdata register is clocked. Confirmed with behavioural sim, this means that stale data is driven out during the first part of a read cycle, before the address is latched.

I "fixed" this by changing the always block that sets outdata to do so on every clock, meaning the right data gets in there during the setup phase while address is valid on the bus, before the OE strobe comes along.

I also refactored my memory bus handling into a submodule (inverting the control signals).

module emif(
    input clk,
    input [1:0] addr,
    inout [15:0] data,
    input ce,           // note these signals are active high
    input we,           // (opposite to the PCB signals)
    input oe
    );

wire drive_data;
reg [15:0] mem [0:3];
reg [15:0] em_outdata;

assign drive_data = ce && oe && !we;
assign data = drive_data ? em_outdata : 16'bz;

// writes data to small mem
always @ (posedge clk)
begin
    if (ce && we) begin
        mem[addr] <= data;
    end
end

// reads data from small mem
always @ (posedge clk)
begin
    em_outdata <= mem[addr];
end

endmodule