It may only have had 128 Bytes of RAM, but it used 4K ROM cartridges, even more than that if the cartridge used bank switching. So Atari 2600 programmes had quite a bit more room to fit inside.
IIRC, early cartridges only had 1 or 2k - the 4k was a limit for a while, but I don't think they all shipped with 4k in the beginning (cost savings). IIRC there was a trick later to allow for 8k cartridges (Pitfall II was 8k, I think, but memory may be failing me).
IIRC, Pitfall II was 2K. 255 different levels in 2K, memorable isn't it ? :)