On the spectrum of languages, C# and Java are really pretty close together...
Don't think of this question like "I want to learn the uber-development platform again, only on Unix instead of Windows this time." For one thing, it doesn't exist (except in Eclipse-land maybe). Unix is all about combining tools and using what is to hand. There's more than one way to do it. In fact, your choices are basically combinatorial as far as what pieces you put together. Don't think of that as a paralyzing decision point, just pick something and start ripping.
For another thing, you will get a lot more out of programming even in the C# environment if you broaden your perspective. Learn some dynamic languages like Scheme or Ruby, learn some new programming philosophies like functional or declarative programming. Learn vim or emacs (I'm an Emacs person, but to each his own), typing text into files, programming without a net.
Just like you can see the von Neumann architecture poking out through C, you can see the Unix way poking out through Perl. You might consider starting with Perl on Unix. You will be able to write powerful programs quickly, you'll have an excuse to get started learning regular expressions (Mastering Regular Expressions is a classic), and the Unix system calls are practically written into the language and docs. Learning Perl, from O'Reilly, would be a good place to start.
I would also strongly recommend learning the command line and bash scripting, not necessarily for the syntax, but for pipes and the core utilities. Classic Shell Scripting, again from O'Reilly, is a terrific introduction.
