The "promise" of web services was that they shouldn't CARE about what language they were written in, or what platform they were running on.
Your "web service" can be written in any language.
However, you chose to implement it in C#. Hence you need a .Net runtime in order to execute your implementation.
Soooooooo -
Mono would be a good choice. Windows and IIS would be another good choice.
Or you can always re-write your implementation in Java ... or Perl, Python, Ruby or C++