FME Server services - is there any required order of services restarting?

The FME Server installer will create the services with defined dependencies, so that they should automatically start in the right order.

You can verify this if you open the service properties and the Dependencies tab, here's an example for the Engine service, which depends on the Core, which again depends on the Database:

For reference, the starting order is

1. FME Server Database
2. FME Server Core
3. FME Server Engines

The FME Server Application Server has no fixed dependency, it will simply retry the connection to the Core until successful (AFAIK).