OK, but I want this to be dynamic: I want to deploy this to my production environment which uses a different web service address, without recompiling it.
Easy, you just make sure that your web reference has the "dynamic" property set and an app.config will be added to your project. Take a look at it. Now you can change the access point via the app.config file. So you just deploy a different app.config file in production. If you are using DLLs and COM interop you can have a lot of fun trying to get the config files loading (see here). If needs be, you can roll your own config file and set the access point URL manually before invoking the web service via the ".URL" method on the web proxy.
OK, but I want this to be really dynamic: I don't know the WSDL at compile-time, all I know is the method signature; I want to provide the WSDL at run-time.
It starts to get a bit ugly now. But if you know the method signature, eg:
public string HelloWorld(string inArg)
then you can define an interface class which you can use in your code at compile time. Then, at run-time, you can look up the WSDL, generate assembly source code from it, compile the assembly and have that assembly implement your interface. Google is your friend here. If found a few examples but this implementation of a WebServiceProxyFactory is pretty darned useful. Note that it does take time to build and compile this proxy assembly - you probably won't be wanting to do this every time, so you may have to implement some kind of proxy-caching.
Hmmm, OK, but I want this to be really, REALLY dynamic: I don't even know the method signature at design time - I want to examine the WSDL and work out which one to use.
Yeah right! Maybe you can get the user to write the code? But seriously, there are times when you might want to call a web service that hasn't even been designed yet - maybe you are deploying your app to a number of clients and allowing them to hook in their own web services calls? It is time to read your SOAP manual. You're going to have to grab the WSDL, interpret it, find the method you want to call, build a soap envelope with your values inserted in the right places, and make the web service call. A quick google of HttpWebRequest and SOAP should get you on the right track. This is no trivial task!