Control two Lego NXTs with an Arduino
You have a number of options.

Since you mentioned you know C# the best, have a look at http://monobrick.dk. They have a C# library that lets you remote control the NXT. Then you could use something like http://playground.arduino.cc/Interfacing/Csharp to do the same for the Arduino. UPDATE: MonoBrick project doesn't seem to be around anymore.
For Java, there is a similar NXT remote control library from http://www.lejos.org/. I imagine you could find something similar for Arduino as well.
If you want to connect the Arduino directly to the NXT, you can use USB or Bluetooth. Then you can use the information in the NXT Bluetooth Developer Kit (available from http://www.lego.com/en-us/mindstorms/downloads) to develop a program for the Arduino what will be able to communicate with the NXT.