I always recommend the following to my customers:
1. Upgrade the SMA on all site servers.
2. Upgrade the site services on all site servers.
3. Once all PS's have downloaded the new agent/plugin packages and the SMP classes them as being ready on the PS's, upgrade the SMA on the clients, followed by the solution plugins on all node types.