My first Apple II had 4k of memory (storing programs and data)
That raises a very interesting point too. The ATmega's Harvard architecture (separate data and program memories) mean that it can be fetching the next instruction concurrantly while executing the instruction it's on even if the current instruction has to do IO. That can also give it a nice speed boost over the 6502 in the Apple II and the 8088 family chips.
and ran at 1MHz. Arduino runs 16 times faster and the latest versions have 32k of program memory and 2k of RAM.
I took a fourth year computer architecture course that can be summed up as "clock speed has nothing to do with computing power".