In general, if you have a particular speed memory interface, then any memory device that can operate at that speed or faster should work just fine.

This is certainly true in the DDR world (mainly due to it being made to a standard) - I have had to support long term products and the fact is memory devices become obsolete very quickly (simply because the vendors are not interested in making slow devices as the market is not there). The slow devices fall off the product listing.

I simply put in devices capable of higher speeds with no issues at all.

I would check the timing parameters, though (for both memory and processor); the datasheet information is the true arbiter of what will work together.

I'll expand on my comment.

A bit of background

Pseudo SRAM is actually a dynamic RAM (DRAM) made to mimic a regular static RAM. Dynamic RAM allows packing much more bits in the same silicon area, so allows for bigger memory sizes (or cheaper price for the same size). The problem is, interfacing with DRAM is a bit more complicated, and, even more annoying, it requires regular refresh of its contents, or you loose it over time. Manufacturers therefore made what is known as Pseudo Static RAM, a DRAM array that has a builtin circuitry automatically refreshing the contents at the appropriate times, and having an additional layer of logic to make the interface look like a regular SRAM.

Differences in operation

There are a bit more constraints when using pseduo SRAM, though. Because the refreshing takes place internally, the reading/writing operations must not be made too slowly, so that internal refreshing cycles can be made in time. See your original chip datasheet: the chip enable pulse width must not exceed 4ms. This constraint doesn't exist in a regular SRAM, you can leave the chip enable active for as long as you want. This difference shouldn't be a problem in your case (it could have if you were doing the opposite: replacing a regular SRAM by a pseudo SRAM).

Now, there is something I must say don't quite understand in the specific case of the original HM65256B chip you have: there are two special operations that are documented in the datasheet: "automatic refresh cycle" and "self refresh cycle". Honestly, I can't really tell why they are here (the datasheet is a bit laconic), since the supposed purpose of a pseudo SRAM should be to hide the details of the refreshing requirements. If you look at the datasheets of today's pseduo SRAMs, you won't see these (there is an internal on-chip timer to trigger the refreshing in time). Maybe the older pseudo SRAM still required the refresh to be triggered externally, I don't know. Anyway, looking at the chronograms for these special cycles, I can say they wouldn't have any effect on a regular SRAM, so it is not a problem either.

There is also one specific data access method I have seen in your original pseudo SRAM datasheet: the "static column mode cycle". Basically, if you change only the A8-A14 lines of the address and keep the same A0-A7, you can access data in a faster time (because you don't change row). In your case, it is 55ns. If the CPU takes advantage of this access mode, then you need to be careful here. Choose a replacement SRAM that has a 55ns access time to avoid problems.

Physical interface

The pinout is the same. So this isn't a problem.

Also, supply voltage, and the input and output voltage levels specified are similar between the original chip and the two replacement chips you suggest. So this is fine too.

Other concerns

The fact the replacement RAMs are qualified as "CMOS" isn't a problem. Your original RAM's datasheet didn't mention CMOS because DRAM is another manufacturing process, but whatever.

Is there a risk of damaging other components? I think the main risk of damage is when you'll desolder/solder the parts. But if the mechanical part goes well, I see close to zero risk that changing the old RAM by the one you suggest will damage anything. In the worst case, it just won't work (for some reason I can't foresee). It could damage something eventually if the contents of the memory read back by the CPU was corrupted, and would indirectly lead the CPU to do crazy stuff with other peripherals somewhere. But this is very unlikely (actually, almost impossible since you said it was video memory).

Choosing a chip with lower access time? No problem. The limit is 55ns, as I explained above. Anything below is fine.

Choosing a chip with more capacity? In theory, it is not a problem either, provided that you maintain the additional address line to a constant logic low (or logic high). However, the problem is that for bigger chips, the pinout is different, so in practice, it is going to be difficult.

Will it change the game experience? No. Games won't go faster if the memory is faster. The speed is decided by the CPU and the crystal.

Conclusion

It you're confident on your soldering skills, and if you choose one of your replacement chip with 55ns (or lower) access time, it is totally worth a try.