This depends a lot on what the cores are. A Pentium III was famously significantly faster than a Pentium IV at the same clock speed.
Assuming the cores are the same other than the clock speed, it depends on your workload. Some workloads can't be run in parallel, and so the 3.5GHz choice is best. Other workloads can parallelize easily. For example, if you have multiple independent trading robots, maybe you can divide the robots evenly onto your CPUs. In this case the dual-2GHz CPU would presumably be better, giving you 2*2GHZ worth of total CPU power, 0.5 GHz of additional performance over the 3.5GHz CPU. If the workload is truly parallelizable then then quad-1GHz CPU would be equally good.
Occasionally you might have four very simple tasks but with strict latency requirements. In this case you would want the four 1GHz cores so you could run all the tasks at once without having to interrupt them for task switching. This is probably a very common goal on VPS because it is hard to get strict latency requirements satisfied on a VPS; VPSs tend to be accessed over internet connections that are much more laggy than task switching time and also VPS may be interrupted to let other users VPS run.