You're remembering correctly, every other logic gate can be built from NAND gates, which is the foundation of this sort of minimal-instruction-set exercise. Beyond that, you need to be able to move data and change your program counter (jump, often conditionally). Then, if you want parity with modern instruction sets beyond just being turning complete, you need return and interrupt for control flow.