I recently upgraded to vSphere 4 in these steps:
- build new virtual machine for vCenter Server (not neccesary but nice with a clean start)
- turn off old vCenter service
- Install vCenter 4 and choose to upgrade the database
- Remove one host out of four in the cluster, install ESX 4 clean
- Run testmachines on the new host
- Join the newly installed host to the cluster
- If it seems stable, re-install the remaining hosts one by one
- Start upgrading vmware tools and virtual hardware on VM's
One caveat is that your current ESX 3.5 hosts requires the old flexlm license server to be installed on the network (or using host licenses) until all hosts run ESX 4. Make sure you have backup for all VM's before upgrading tools/virtual hardware and take each step slow and you'll be able to upgrade with only one controlled reboot of each VM, no additional downtime is needed. There's the possibility of upgrading ESX but I prefer to do a scripted install to get a truly clean machine.
I also suggest you read the upgrade documentation (http://www.vmware.com/pdf/vsphere4/r40/vsp_40_upgrade_guide.pdf) for lots of pointers on database upgrades and so on.
Good luck!
