RS-232 is generally slower than parallel, but in this case the speed of the HP-41 will be the limiting factor anyway so it doesn't matter. RS-232 requires fewer connections (a minimum of transmit data and receive data, two wires, not including ground), so I would go that way if the Arduino has RS-232 capability (including the line drivers and receivers). The 164 gives you the RS-232. The 165 and 166 are parallel.
On a note that is related and probably of interest on the Arduino but not directly applicable to the 41, synchronous serial (as opposed to asynchronous serial like RS-232) interfaces are very popular today for communicating across a PC board (not so much across a room) because they require fewer connections than parallel interfaces, and the fewer pins on the ICs also means you save board space. When you're breadboarding, it also means less labor.
Dallas' 1-Wire interface puts the clock and bidirectional data and sometimes even power on a single wire, but it is very slow, timing-critical, and really only suited for something like digital thermometers which can't change fast so there's no sense in requiring fast communication. Still, each device has a unique address it responds to, and you can have lots on a single wire. It seems extreme to me, taking it a little too far.
I²C uses a clock line and a bidirectional data line, and, although it's much faster than 1-Wire, is usually limited to around a megabit per second.
SPI uses a clock line, data in, data out, plus a select line for every device, meaning at least four lines but one additional one for every device after the first. It sometimes goes over 50 megabits per second, so it's definitely fast enough to store the data on an SD card when you're taking video on your digital camera. Since no line is bidirectional, logic-level translation between different operating voltages is easy too. Microwire is closely related to SPI and Microwire and SPI devices can be put on the same interface.
There are others, but I²C and SPI are the most common, and there are thousands of ICs on the market that you can take advantage of, for things like EEPROM and flash memory, reat-time clocks, relay drivers, keypad scanners, displays, digital potentiometers, A/D and D/A converters, UARTs, USB interfaces, general-purpose I/O expansion, programmable-gain amplifiers, signal generators, etc.-- you get the idea. It's easy to bit-bang these if you have to, but doggone it would be slow to do it on a 41!
Edited: 13 Jan 2012, 2:08 p.m.