Since this is development of a new application, it simply should not be done using the Web ADF. Aside from being much less straightforward than the Web APIs, its shelf life is very limited at this point. Since your development environment is Visual Studio, I would recommend that you take a look at the Silverlight API. Not only will your development experience be much less painful, but you'll also be able to provide a much richer user experience than with the Web ADF. If a browser plug-in is not an option, then use the JavaScript API.
With any of the web APIs, reordering layers is simply a matter of manipulating the Map object's layer collection. I strongly agree with Michael and Brad, however, that allowing users to pick and choose from many layers usually makes for a poor application. An exception would be if you have a "designer" or "administrator" role, where users within this role are experts that make meaningful subsets of layers to share with the bulk of the application's users. Examples of such an approach can be seen in Esri's Explorer Online or SharePoint products. Another exception would be if the repository of layers to choose from is small. If your application does not fall into one of these categories, I would suggest that you are doing your employer a disservice by not pushing back hard on this requirement.
On the subject of the acceptability of browser plugins, this is less and less of an issue in government as more agencies, including the US armed forces, have approved use of Flash and Silverlight in application development. Plugin adoption is recent for many departments and agencies, and in some cases is not widely known by their employees. So if you receive an indication that using a plugin is not an acceptable approach, you or someone on your team should double-check this against the agency's technical guidelines.