Salting slows down dictionary attacks. It doesn't make them impossible.
If the site is able to verify a password with reasonable effort, an attacker that stole all relevant data is able to check a password with that level of effort.
Without a salt, an attacker has to spend the effort once to check against all users' passwords. A salt doesn't meaningfully increase the cost to check against a specific user but slows down attackers (who want to check a password against all users), so yes, you should have it. Additionally, you should use "expensive" hash functions. If you use 28999 iterations of PBKDF2 with SHA256 (an example config that I found in a benchmark, far from the state of the art but likely still very common), that means trying the 1000 best guesses against your million users is 10000 * 1000000 * 28999 hash calculations. Unfortunately, a RTX 3090 can do 129400 sets of 28999 iterations per second, so trying the entire dictionary against all users will take less than a day (https://gist.github.com/Chick3nman/e4fcee00cb6d82874dace7210...).
Even with a better algorithm, if you expect to be able to log in 100 users per second on your server (spending all resources on password hashing), the attacker will be able to test at least 100 passwords in the same time using the same resources (realistically more, because the attacker will likely have a better optimized setup, since their machine does nothing else but try passwords while yours is optimized for something else).
Let us say you do unix style passwords - generate random salt and store the salt with the password. Hashcat can run through 54 billion md5 hashes/17 billion sha-1/7 billion sha-256 hashes on a single pc per second.
Asking people to change the password as a precaution does not sound bad at all.
