A system, comprising: a plurality of instance hosts (110A, 110B, 110C) configurable to implement resource instances of a network-accessible service; and one or more control servers (120A, 120B, 120C) configured to manage configuration of resource instances at the plurality of instance hosts; wherein a selected control server of the one or more control servers is configured to transmit, in response to an instance configuration request from a client, a sequence of one or more commands to a selected instance host of the plurality of instance hosts; wherein the selected control server of the one or more control servers is selected in the proximity of the selected instance host; wherein the selected instance host of the plurality of instance hosts is selected based on at least one of an identification information of the client, a resource instance type indicated in the instance configuration request, an availability of the resource instance type at the instance host, a location of the instance host, a utilization level of individual ones of the plurality of instance hosts, and an explicit location preference indicated by the client; wherein the selected instance host is configured to, in response to receiving the sequence of one or more commands, instantiate a remote command executor; wherein the remote command executor is configured to initiate one or more configuration operations corresponding to the sequence of one or more commands; and wherein the selected control server is configured to provide a response to the instance configuration request, based at least in part on results of the one or more configuration operations, to the client. a plurality of instance hosts (110A, 110B, 110C) configurable to implement resource instances of a network-accessible service; and one or more control servers (120A, 120B, 120C) configured to manage configuration of resource instances at the plurality of instance hosts; wherein a selected control server of the one or more control servers is configured to transmit, in response to an instance configuration request from a client, a sequence of one or more commands to a selected instance host of the plurality of instance hosts; wherein the selected control server of the one or more control servers is selected in the proximity of the selected instance host; wherein the selected instance host of the plurality of instance hosts is selected based on at least one of an identification information of the client, a resource instance type indicated in the instance configuration request, an availability of the resource instance type at the instance host, a location of the instance host, a utilization level of individual ones of the plurality of instance hosts, and an explicit location preference indicated by the client; wherein the selected instance host is configured to, in response to receiving the sequence of one or more commands, instantiate a remote command executor; wherein the remote command executor is configured to initiate one or more configuration operations corresponding to the sequence of one or more commands; and wherein the selected control server is configured to provide a response to the instance configuration request, based at least in part on results of the one or more configuration operations, to the client.