Set-Service: Cannot stop service because it is dependent on other services

The Set-Service cmdlet is for changing the configuration of a service. That you can use it to stop a service by changing its status is just coincidental. Use the Stop-Service cmdlet for stopping services. It allows you to stop dependent services as well via the parameter -Force. You'll need to retrieve the service object with Get-Service first, though, since Stop-Service doesn't have a parameter -ComputerName.

Get-Service -Computer appserver -Name MyService | Stop-Service -Force

I eventually resolved this problem with the following code, which calls sc to stop the service and then waits for it to finish stopping. This achieves the same result as expected from Set-Service -Status Stopped; that is, when it returns the service has been stopped. (sc on its own starts to stop the service, but does not wait until it has finished stopping.)

Start-Process "$env:WINDIR\system32\sc.exe" \\APPSERVER,stop,MyService -NoNewWindow -Waitwhile ((Get-Service -ComputerName APPSERVER -Name MyService | Select -ExpandProperty Status) -ne 'Stopped') {    Write-Host "Waiting for service to stop..."    Start-Sleep -Seconds 10}