What are the practical consequences of rewriting Git history?

As mentioned in the other answer comments, in practice each commit is unique and rewriting history will make new commits.

You can think of it as cutting off the branches of a tree and then instantly growing new ones. They may even look the same but aren't. Yes, voodoo magic. In this analogy, reverting would be almost like supporting a falling branch with a log, so it will grow its way without falling down.

That leads us to a couple good reasons to rewrite history:

• Slim down a private repository before going public: for instance, create a new local private branch, test, test, rewrite, push.
• Remove sensitive data from a private repo before going public.

Those already reveal what Greg already said: rewriting history will potentially screw up everyone if the repository is public (pushed commits). Reason why I also advocate on avoid doing it at all costs even in private repos, just to keep the good habit: and so rewriting history should be avoided at all costs ^{(this means to just give enough consideration before doing it: weight up the pros and cons!)}

And there is at least another philosophical and overlooked reason: rewritten history is data lost. True, a git history with revert might look messier than a reset one. But if properly written, all that "mess" can be hidden away in separated branches and still we can see precisely at what point a revert was done. And even with reasons or evidence as to why it was done.

Back to the tree analogy, even if you do remove the supporting log, the reverted branch will show the sinuous growing curves, and it is beautiful!

Required reading is Problems with rewriting history in the Git User's Manual.

If I rewrite history (and everything compiles/works in all affected branches), will my co-workers need to do any special commands (i.e. will they "know that I have done it" if I did it well?)?

They will know, and Git will tell them in no uncertain terms that something is wrong. They will get unexpected error messages, and may in the process of trying to resolve the resulting merge conflicts, inadvertently revert previous commits. This problem creates a real message, and if you're curious to see what happens you can always try it on a temporary copy of your repositories.

Will any users with local changes that I do not know about be eligible for merge failures on git pull ?

Absolutely, see above.

Am I missing anything essential here ?

Avoid rewriting history at (almost) all costs!