1: Is the mega 2560 the best option? From what I've read I could use say a UNO and soft serial. Not worried about the price difference, but a smaller package would have advantages.
Probably, given that the Mega models have three hardware serial ports. The advantage of the hardware serial port is that it can buffer 64 bytes of data and is less processor intensive.
2: Can I simultaneously monitor the data on my PC using the USB, or would I have to use a serial connection?
The USB connection emulates a serial port. From the perspective of your Arduino program or programs on the PC it just looks like another serial port.
3: Do I need MAX232 for each UART I use? (Presumably I'll use two UARTs depending on the answer to question 2).
Your various units should specify if the serial port is RS232 or TTL. RS232 signals are +/- 12V while TTL signals are 0 to 5V. If it's RS232, and usually it is if the serial cable is long, then you need the MAX232 board, and one for each connection. Also, you can never have multiple units using the same RX or TX pins -- they can't share.
4: For the parsing it looks like TinyGPS+ would be of great assistance. Is there any issue using it and the hardware UART's?
It'll be better using hardware ports. Anywhere the TinyGPS library shows "SoftwareSerial" just replace with "Serial" (or "Serial2", etc.).
5: Being in a marine environment, I plan to seal it all in a water tight box when done. Will this present cooling issues on a Mega 2560 (or a UNO)?
I've never heard of anyone using heatsinks or having cooling issues with any of the Arduino chips. You're likely to have problems with condensation though, so if you happen to come across any silica gel packs you should throw those in the box to help protect things.
3.5.5 Maximum Voltage on Bus
The maximum applied voltage between signal lines "A" and "B" and between either line and Ground shall
be in accordance with the EIA-422 specification.
For protection against miswiring and for use with earlier TALKER designs, all receive circuit devices
should be capable of withstanding 15 volts between signal lines "A" and "B" and between either line and
ground for an indefinite period.
This is RS422 which has the same voltages as RS232 but uses four wires instead of two, but you can't use an RS232 board for RS422. See http://arduino-info.wikispaces.com/RS485Info
for help with RS422.
"NMEA" just specifies the format of the messages -- not the wiring. Don't get into the thinking that if a device uses NMEA messages that the wiring must be RS232, TTL, or anything else.