Mongo as service error: Cannot determine state of server

On the current primary node of the replica set, you may issue the rs.remove() for those nodes, and thereby stopping replication attempts to them.

You will probably have to shut down the server that you want to run in single mode, and start it up again without the --replSet <name> option (or whatever it might be set to in your config file), as this will start the server in single mode, and not try to replicate to any other nodes.

I'll take these one at a time:

Should each config server have auth enabled?

Yes, basically every instance of mongod you run should have auth enabled (and keyfile, which implies auth).

If so, then setup the same user across each? Just for the admin db? Or is there a need to create one for the config database?

The admin database in a sharded environment will actually live on the config servers. Hence you will have a copy of the admin database on all three (they will be identical to each other). You should always be connecting to the config database through the mongos and you will not be creating other databases there, so no need to add specific users.

I am guessing you don't need to create any users while on the mongos, since it should inherit from the config and the shards themselves, is this correct?

The first shard you add, if it has existing databases, will be the primary shard for those databases (forever). That primary shard will contain the authentication records for those databases, even if you subsequently shard the collections across multiple shards. Any subsequent databases that are created after you shard may live on another shard, and their credentials will be stored there. Basic rule of thumb is: use mongos to manage your users in a sharded environment.

Note: The above is true in MongoDB 2.4 and below. The planned changes in 2.6 will centralize all credentials to the config database in a sharded environment and remove some of the complexity. However, the rule of thumb is still applicable, use mongos

When adding a new shard, is it needed to go and setup the same users for each sharded database on the new shard?

As the answer to the previous question implies, no this is not necessary as long as you always connect via mongos (recommended - it knows what the primary shard is for each database and will route your auth request appropriately). There are some edge cases where you might need to have the users on all shards, in which case you would have to add (and maintain) them on each shard, but for general use it is not required.