You don't mention exact numbers, so I don't know if we're talking about 10 machines, or 1000 machines, which could have a big impact on the best way forward. As such, I'll keep this relatively general.
First off, unless you have a lot of manpower and a big budget, trying to replace everything all at once is going to fail. That's a huge undertaking, and I would strongly recommend against it.
What you want to do, is start in the 'center', and work your way out. First come up with a minimal central server configuration, and build that out. Minimal recommendation, if these don't currently exist, would be a file share and e-mail system. Assuming that nearly all of the machines are running some flavor of Windows, you probably want to get an ActiveDirectory Domain Controller setup so you can set a few basic security and corporate computing policies and push them out.
From there, take it one machine at a time, and work to get them added to the domain, and configured to access the corporate fileshare and e-mail system. Eventually you'll have all of them talking to the servers, and you can then come up with some better policies towards standardization and consistency. Also, as you go through this, make sure you take as complete and accurate of an inventory as you can. This will aid you immensely with asset tracking and management, and if things are as big of a mess as it sounds, you'll likely want to be doing your own software license audit soon, too.
Again I want to stress the importance of breaking the project up into small tasks, and taking it one step at a time.