The NES used a 6502-derived CPU at 1.79 MHz.
The Sega Master System used a Z80 at 3.58 MHz.
How did they differ in terms of what speed grade ROM they required in their respective cartridges? I know it's not as simple as just taking the reciprocal of the clock speed and saying that's the required access time. For example, the 6502 accesses memory during only part of a clock cycle.
The calculations are not that simple.
Nintendo used a custom CPU whose timing is not specified in a publicly-available data sheet. If there is no data, we can't know the required ROM chip timing that will provide CPU data quickly enough.
The Sega case can be analyzed. They used both Zilog and NEC CPUs. For instance, there are photos of one system with NEC uPD780-1 CPU, which is a 4 MHz version necessary for running it at 3.579545 MHz. The data sheet with timing parameters is available for anyone to verify the calculations.
If we make some assumptions about an ideal system, with exactly 50% duty cycle clock and no time spent on decoding the memory address to ROM chip select, we can do the following calculations.
The fastest read cycle without wait states is two clock cycles, or the 558 ns mentioned in the other answer.
But that isn't the memory access time.
From the two full clock cycles, both /MREQ and /RD are active for only 1.5 clocks (419 ns).
In addition, it may take up to 85 ns after the clock edge before /MREQ and /RD are both asserted. So that leaves 85 ns less for the ROM chip access.
Then the data bus must be stable for some time before the clock edge that latches in the data. This is either 35 ns or 50 ns, depending on cycle type. I will take a shortcut here and state it's 50 ns, even if 35 ns might be enough. So that is another 50 ns less time, from the moment the ROM got the read signal.
So in order for the CPU to reliably see the data before it is too late, the ROM must be able to provide the correct data on the bus in 419-85-50 = 284 ns.
In practice, it must be even faster. It takes time for the gate array IC to decode the Z80's address bus and /MREQ into a chip select for the correct ROM chip in the memory map. If this was done with a typical CMOS IC like the 74HC138, it would have a typical propagation delay of about 15 ns, but it could be up to 50 ns.
Also, as the CPU clock does not have to be a 50% duty-cycle square wave, the high and low portions do not need to be equal. At the ratio limit of 45:55, the 1.5 clock cycles can be about 14..15 ns faster.
So with all that time getting spent elsewhere, even a ROM chip with 250 ns access time will not work under nominal operating range. Maybe a 200 ns chip would work.
They'd both be the same, 558 ns or 1.79 MHz.
The 6502 performs each memory operation in one clock cycle, using the rise and fall to space out pulling the address bus vs the data bus. Unlike some home computers the NES doesn't have the 6502 sharing its bus with another device so there is no clock cycle splitting to take into consideration (if it could split the bus it wouldn't have the bugs related to the audio DMA interrupting the CPU at bad times).
The Z80 takes a minimum of 2 clock cycles for each memory operation, one for setting the address and another to either read a value or to be sure enough time has passed for a value to be written (the NES PPU works like this too). So it ends up being the same speed as the NES.
