Well, something like 8k of ROM and 2k of RAM was enough to go to the moon, land, take off, and come back, so...
That's what people have the disconnect on. Flight control software isn't stressing. It's maybe a dozen or two 6x6 matrix-vector operations which unroll into maybe a few hundred FLOPS (or they could be fixed point) that need to run maybe at 20 or 30 Hz (Apollo's major cycle was 10 Hz). This is stuff you could do with hand-wired 7400 IC's if you really wanted to (in fact they did the equivalent for the first submarine launched ballistic missiles in the 50's). Having a programmable computer that's fast enough to do it a few hundred times a second, and handle the control loops for some of the other stuff in the capsule is nice, but it isn't hard with a 10 MIPS processor, let alone the 200+MIPS they're flying in ORION.
In the 60's when they went to the moon, it was hard because there was no such thing as an off-the-shelf space-qualified programmable flight computer, so they had to invent it all from scratch, and there's this mistique that developed around it. But even by the 80's and 90's, the space hardware and avionics industries advanced to the point where the hard stuff was knowing what software to write, not finding a computer and inventing a compiler to run it on.