I) Topshelf is an open source project for developing Windows Services easily. It will save you time and even if you decide not to use it, you can learn from it's source code.
II) The short answer is you have to poll the status of the other service. There is no (plain) event based mechanism for this.
If you can not make any modifications to the other service then you can poll over it's status by (in a separate Task):
var sc = new ServiceController(serviceName);
status = sc.Status;
And use the answer you've mentioned to restart yours (and again poll in OnStart until the other service get started completely).
But if you can modify the other service then you can use other means like pipes or named mutexes to do that (again needs polling in a separate Task or at OnStart and probably at OnStop).