Recommendation for Arduino
It seems like you've largely answered your own question.  The Mega is by far the biggest and most powerful of the Arduinos.  Personally I lean more towards quantity instead of quality, so I'd get two less expensive Arduinos.  I find the female headers on the arduinos somewhat limiting, so the various breadboard Arduinos tend to get my nod (Really Bare Bones Boarduino and Boarduino).  You're usually choosing two things when you pick an Arduino:  how many inputs/outputs it has and how to communicate with it.  You're obviously on top of the i/o questions, but you might want to think about whether you're going to use USB or serial (probably via USB -> serial adapter) to program the Arduino.  If you're only going to buy one or two boards, then USB is the easiest and cheapest.  If you're going to end up with 3 or more boards, it's probably cheaper to buy serial-only boards and a separate USB -> serial converter (FTDI cable or FTDI basic breakout board).

The base Arduino is amazingly capable and it's pretty easy to add additional inputs with cheap multiplexer ICs.  If you don't have immediate need for the extra inputs, it might be worth starting with a cheaper board.

If you're using the Arduino IDE, then you'll be programming in C++ on all the Arduinos.  The Arduino documentation tends to encourage using only slightly more than the C subset of C++ (basically C with just one or two extras), so a C programmer should feel very comfortable.  As an added bonus, you can do things like declare variables right before you use them, rather than having to do so at the start of functions.  On the other hand, watch out for differences from the C standard library.  sprintf("%f", foo) and some other things don't work by default.  When in doubt, hit arduino.cc and search.

As for communicating back to the computer, I'm personally using Ruby on Rails to talk to my Arduino projects, but most folks seem to prefer Processing.  It all boils down to a serial port, so you can use whatever you feel most comfortable with.