I'm planning to install Update 4 to my HA ESX 3.5 environment and was looking for some best practice advice if possible.
Is it better to put the ESX servers into maintenance mode when doing the upgrade?
In every host related update/upgrade procedure you have to use maintenance mode.
If you have VC and VUM see this procure:
I am a little confused, Do you want to apply update 4 on esx Servers or you want to upgrade your ESX 3.5 Servers to ESX 4?
If you are going to apply the update 4, I belive for ESX 3.5 there is another update as well (update 5) and they both released long time ago.
The link that Andre provided you is to help you with Upgrade your ESX Servers to ESX 4 (VMware vSphere 4).
In any case I recommend to read the documentation from VMware.