It's not actually a true "either this or that" question since you can actually use both together via watir-webdriver.
Firstly:
If we are talking about testing at the browser level, you can pretty much completely ignore the language used to run the server side. There's no C# remaining once the page is rendered to HTML+Javascript and sent over HTTP to the browser. So there's no need to use c# as your test automation language. (you might still want to, but you don't NEED to)
Secondly
Purge the idea of record/playback from your requirements. In the long run it just doesn't work for anything above the level of the HTTP protocol (recorders are fine at the protocol as a starting point in a loadtest scenario, but not for function testing at the UI level) This is something most experienced testers have known for about 15 years now and is an area of broad consensus among experienced QA people. The resulting tests are brittle and hard to maintain. The only people that like record/playback are salespeople of vendors of tools that depend on that level of tech who use them to convince managers that with their tool, "anyone can do test automation" IMHO the whole reason the Selenium IDE/Recorder exist is to compete with that mentality, few Selenium users I know use it, or the older Selenium Grid.
So what language do you use?
With that in mind, use whatever works best for your testers, and dovetails with whatever frameworks you are using such as FITNess, or Cucumber etc. Personally I think that Ruby is an excellent language for testers to script in because it is easy to code and learn. Thus if your QA folks are not experienced coders, it may be a better way to go than trying to teach them C#. Also the Watir API is very object oriented and easy to understand for anyone that has grasp of HTML and the DOM (Domain Object Model) of a webpage. I'm also using cucumber to do BDD, which is done in Ruby so that dovetails well with Watir. OTOH if the people that will be doing this automation know another language, then you might want to go with Selenium RC and that language.
edit: The biggest factor in deciding what language to use often comes down to 'who do you want working on tests' If you are fine with silos and having just your testers or SDET type folks work on E2E automation, then pick whatever language works best for them. OTOH if you want your developers to be able to fix tests they are breaking with UI changes etc, then you may want to pick a language common to what your dev team is using. With agile teams using embedded testers as a part of the team, and not doing handoffs, that sort of thing can be a much larger concern going forward. Also there are now Java and JS versions of tools like Cucumber, so you have new options there these days as well. (this is something that has changed a lot in the 5 years since I originally authored this answer)
Enter Webdriver
The thing is that Watir and Selenium are closer than many people realize, especially now that the Watir-Webdriver gem has arrived which uses Selenium's new Webdriver technology (which as I understand it, is also replacing Selenium 'Core') to drive the browser under the hood, but allows the tester to write code in ruby with the excellent Watir API. With both Watir and Selenumn moving to Webdriver for interfacing with the browsers, it appears to be the future of both projects. Using Watir-Webdriver gives you IMHO the best of both worlds, with wide browser support due to Webdriver and the easy coding of Watir.
I'd try the tutorials of both (Selenium RC and Watir) and see which API seems like it would be easier for you to use for coding your tests. If you like Watir better, be sure you immediately adopt using it with Watir-Webdriver as well.
