Let's say that I want to introduce OpenOffice.org to an organization that already has site licenses for Microsoft Office. I'd talk about it in terms of money: that is, how much people would save if they switched. I'd give them some time to try OpenOffice.org out in order to see if they can survive a year without Microsoft Office. It'll be up to them to figure out what to do with OpenOffice.org, but they can form support groups if they want.
Because site licenses depend on the number of seats, I'd keep a running count of the people who signed up for the program so that we can see the prospective savings. I'd pass those savings directly to the employees' monthly salaries so that they can see the effect. It'll cost more initially—think of this as the cost of training.
This makes the benefits of open source tangible and rewards people who are open to change.
I'd keep at least one Windows machine with Microsoft Office around so that people have somewhere to go when a client sends them something braindead. However, I would post a sign warning people about viruses, and do an anti-virus sweep frequently (every night?). The results of this would be posted.