I'm going to run out of pins on my usual favourite, the Leonardo, so I need to go for something bigger plus a bit more memory might be useful. A quick google suggest the Mega may be best for me as I can use my existing 5v plug in modules but that isn't a deal breaker for this project. Probably the Mega2560 Rev3. Are there benefits of other Arduinos or pitfalls on this one that I might be missing?
As long as you're not using the native USB functionality of the 32u4 on the Leo, the Mega would work if you need more pins. The other big board is the Due but it has 3.3V logic.
You could also use an I/O expander like this: SparkFun 16 Output I/O Expander Breakout - SX1509 - BOB-13601 - SparkFun Electronics
It uses I2C so wouldn't use any of the pins that you're currently using.
I like the 1284P, dual hardware serial ports 16K SRAM, 128K flash, 4K EEPROM, 32 IO.
I offer boards in several form factors, here's a couple:
http://www.crossroadsfencing.com/BobuinoRev17/
Small DIP form, shown with right angle FTDI Basic, can use straight pins also.
One more things to verify before moving your project on another board, if libraries are compatible with new platform.
Another "bigger" board that I really like is the Digilent chipKit uC32, although MasterT's point about libraries is a biggie there, as the uC32 is a PIC-based board with a very different programming model.
The Mega 2560 has some unique features, like the ability to integrate with external memory devices using a relatively conventional 16-bit address bus / 8-bit data bus. That happened to be extremely useful for the project I'm working on now, so the 2560 was the clear winner.
Those 1284P DIP modules look pretty slick, too.