I am pretty sure the best place for you guys to start would be with a kit, instead of trying to tackle the entire project from scratch. Even with a kit, I'm sure you will run into quite a few challenges that you may not have anticipated. The kits that have been released in the past few years are excellent learning tools, with great online communities for support when you are troubleshooting.
I don't have direct experience with many of the kits other than the Vex (which is pretty expensive, but very flexible and has a HUGE community) and the Parallax Boe-bot (which is a simple robot that might not appeal to you, but is fun in its own right.) Of course, there's always the excellent Lego NXT, which is hardly a mere toy! Maybe pick up an issue of Robot magazine and take a look through the ads. I've seen some awesome Mech warfare robots in the magazine too (airsoft cannons in miniature scale cities; http://robogames.net/rules/mech-wars.php
Just something that I'd say is worth considering. (If you want to get started for "free" then you could give ROS with the Gazebo simulator a try. But the learning curve is steep, and it really isn't well suited (yet) to the beginner. Theoretically you could design and test your robot entirely on your PC without buying a single part or even stepping outside!)