To be blunt, this sounds like you're looking for reasons not to do it. Just get NUnit and get going. Start with the smallest piece to get your feet wet.
TestComplete was decent and easy to use when I used it (a couple of years ago). At least then, you'd need to learn some VBScript.
We use TestComplete from AutomatedQA, and it's a decent platform for doing gui testing. We do all of our TestComplete code in Jscript, which isn't great, but it gets the job done. I'm not sure i'd recommend Automated GUI testing though, I think you'll get a much better return on unit testing.
Nunit and rhino mock are great tools for unit testing.
CruiseControl looks like the best way to set up automated testing on each build.
Gallio is actually a framework for the entire testing toolchain. From writing the tests, to running them to post build processes. It provides common facilities and standardized interfaces for each step to allow greater choice and flexibility when putting a build process together.
It comes with a version of the MbUnit framework, which it uses by default. It also comes with a GUI runner named Icarus, and a console runner named Echo. They are all well respected tools in the testing community.
It is an excellent choice for a large company, since it can allow you to take advantage of many of the popular testing and continuous integration tools with a minimum of integration headaches.
Picking a framework and writing tests is only half the battle, Gallio really does help with the other half; gluing up all the other steps in the build process.
The only real downside at the moment is the lack of a central repository of examples and information. For some, the fact that its a relatively new initiative may put them off using it right now.
Check out the docs here. They are a work in progress and very incomplete but will get you started on the basics of writing tests. Keep your eyes on Jeff Browns Blog for other information.
I would recommend to take a look at Ranorex. It is a GUI test automation framework for testing many different application types (Win32, Winforms, Web 2.0, WPF, etc.). Since Ranorex is a .NET based automation framework you can write your test code also in C# and VB.NET and combine it with your unit tests.