I find that the C# times reported by the judge are generally 10x the time of the same algorithm in Java or other languages. This must be an artifact of whatever runtime they are using (mono?) - there is really no general perf difference between C# and Java in normal circumstances.
The trivial solution to this problem (group strings by sorted version of string) is about 5 lines using Linq, but it times out and isn't accepted. It's very similar to an accepted python solution (and yours).