You don't need multiple instances of your service. From the description of your problem it looks like what you need is one service that can impersonate users and execute jobs on their behalf.
You can do this by implementing a COM object hosted in a service. Your client application (that the end user runs) will call CoCreateInstanceEx on your CLSID. This would cause new instance of your COM object to be created in your service. Then the application can use a method on one of your interfaces to pass the collected user credentials to the COM object (though I'd be wary of collecting credentials and instead see if I can pass the user token instead). The COM object which is running in the context of the service can then call LogonUser() to log on the user and impersonate it, so it can do whatever on her behalf (like finding the user local appdata folder :-)). Other answers havve good links to impersonating users using credentials or token.
If you feel comfortable with COM, I'd suggest you create your objects as multithreaded (living in the MTA), so that their execution is not serialized by COM. If not, the default single threaded model would be good enough for you.
The Visual Studio ATL wizard can generate the skeleton of a COM object living in a service. You can also read about implementing Windows Service with ATL here: http://msdn.microsoft.com/en-us/library/74y2334x%28VS.80%29.aspx
If you don't know COM at all, you can use other communication channels to pass the credentials to your service.
In any case, once your service gets the credentials, all the work on behalf of the user will have to be executed on a background thread, so as to not block the application running as the user.