The first step should be to follow your organization's Information Security Incident Response Plan. If you've never tested it before, it will likely be lacking in some things, so be sure to take notes as you go and update it after the incident. Your company's next step should be to bring in an outside security response firm to help navigate the problem.
Until they arrive, you need to start by locking the attacker out completely. Isolate the entire forest of Active Directory servers from the rest of the network. Create brand-new dedicated accounts for your domain admins to use strictly for domain administration purposes going forward, and then remove domain administrator authority from all users, including yourself. Take a copy of the Active Directory logs, so you can figure out which accounts he may have accessed, changed, or used. Those accounts are obviously your priority for password changing.
Now you can reconnect your AD servers to the network. From this point forward, use only those special accounts for domain administration tasks; and never use those special accounts to log in to any machine that isn't an AD server.
Never grant domain admin privileges to any account that can be used to login outside of the AD servers. Instead, use the new accounts to manage the domain by local login only. The reason for this is it's likely the attacker compromised a workstation that one of your domain admins had logged into. The attacker then used a pass-the-hash attack to log on to your AD servers, and that's when it was game over for you. You never want your domain admin credentials exposed outside of the AD server environment.
Next, close down the attackers entry and exit points. Shut down or disconnect from the network any compromised machines; depending on the data in those machines you may have to preserve them as evidence. You'll also have to figure out what he took, gather evidence, report it to the appropriate authorities, send out breach notifications if required, etc., etc., etc.
Only after you've done those first response steps is it time to think about having your users change their passwords.
There is an easy way to get the rest of your people to change their personal passwords: send out a notification to everyone that you will be requiring them to change their passwords, then set the "User must change password at next login" flag on all accounts that allow interactive login. A few days after you've notified them, you should lock out any accounts that still have unchanged passwords. Any remaining affected users will have to call your help desk to unlock their account before they can log in.
You'll also probably have a lot of non-user credentials in your organization. These are the service accounts for all your back end systems, and they all need to be changed, too. You'll definitely need to find the technical owners of each of those systems, and work with them to make the changes. Changing dozens of non-user passwords is one thing, but changing thousands of them is way too big a task for one person. You'll need organization. You'll want to assign security people to each handle one or more of the various divisions and departments. If you don't have enough security staff, you'll have to deputize some of your trustworthy technical folks.
You also will need to scan all the machines in your domain; review every member of the Administrators groups you find; and discover any local accounts (administrators or not.) The local accounts need to have their passwords changed, too. You could enforce this by sending a group policy to the domain-joined machines to require local accounts to force a password change.
But don't involve your users until after you're absolutely sure you've secured your systems, and you know the intruder can't return. You are not only wasting their time if you have them do it twice, but you're appearing to them like you're scrambling. There is a huge psychological blow to people when they've been violated, and you will need to outwardly project an image of situational control. "Uh, hey guys, can you all change your passwords again?" is not a confidence builder among the troops.