There are a couple different unintuitive things going on here.

First of all, your command to the remote host is parsed as

(sh -c echo starting); who -b; date; echo $SHELL

The outer quotes are stripped away leaving you with only echo starting run in sh which is why $SHELL is set to /bin/bash.

Secondly, "starting" isn't printed for the reasons stated in this answer: http://unix.stackexchange.com/a/253424

However, you can fix both of these problems by simply wrapping the command in another set of quotes, leaving you with

ssh myhost sh -c '"echo starting; who -b ; date; echo $SHELL"'

Though I would argue it's more clear if you move the single quotes out to encompass the sh command:

ssh myhost 'sh -c "echo starting; who -b ; date; echo $SHELL"'

There are a couple different unintuitive things going on here.

First of all, your command to the remote host is parsed as

(sh -c echo starting); who -b; date; echo $SHELL

The outer quotes are stripped away leaving you with only echo starting run in sh which is why $SHELL is set to /bin/bash.

Secondly, "starting" isn't printed for the reasons stated in this answer: https://unix.stackexchange.com/a/253424

However, you can fix both of these problems by simply wrapping the command in another set of quotes, leaving you with

ssh myhost sh -c '"echo starting; who -b ; date; echo $SHELL"'

Though I would argue it's more clear if you move the single quotes out to encompass the sh command:

ssh myhost 'sh -c "echo starting; who -b ; date; echo $SHELL"'