Is it possible to create a standalone, C# web service deployed as an EXE or Windows service?

Yes, it's possible, you may want to have a look at WCF and Self Hosting.

Yes, it is possible (and fairly easy).

Here is a CodeProject article showing how to make a basic HTTP server in C#. This could easily be put in a standalone EXE or service, and used as a web service.

One technology you might want to check out is WCF. WCF can be a bit of a pain to get into but there's a great screencast over at DNRTV by Keith Elder that shows how to get started with WCF in a very simple fashion.

http://www.dnrtv.com/default.aspx?showNum=135