Should you replace a whole department's PCs or half?

There can be no one answer to this situation. Where I've worked it's normally a case of staggered replacements, rather than an entire department at one time. It's often also smart business because the expenditure can be spread over time.

The dual monitor issue should be looked at independently of the workstation upgrades. If there is a business case for running dual monitors why not simply install a suitable graphics card and buy a second monitor? That's no reason to replace the entire machine.

How about only replacing half of the computers, but giving everyone a second monitor? A decent dual-screen video card costs maybe $50, so you are defintely saving a lot of cash here while keeping people happy.

You didn't specify what does your company do, but unless its something very resource intensive, most people wont even see much difference in performance on the new PC.