I was impressed by the simplicity as well. I think Gale & Shapley's intellectual contribution was not so much in proposing the algorithm, but in proving that a stable match is alway possible (and that this algorithm generates one such match).