Send email to all users with specific role (updated privacy policy)
Mass contact is probably the way to go for you, if it has to be a solution integrated into the site. Categories are really easy to configure. 

Automated and integrated solutions are always recommended over hacks, but if you're really doing this only once, the fastest way would be to export email addresses and use an email campaigning service or design and send manually in batches (sending bulk emails are limited per hour for spam reasons) from your site email address but that is difficult to test. 

Setting up the HTML styling for your email is what you'll spend most of your time (through Mime mail module). If you plan on testing it on various email clients that is. Many services (Gmail for example) strip styling from emails, so you have to be careful what you style and how. Usually you use a tool that takes your email CSS and applies it all inline, because that is the most reliable way most of the styles will "survive" various email client filtering. 

Simplenews is a very comprehensive solution, much much more to configure and understand there than Mass contact. 

I can't see configuring Rules to be triggered would be easier than using Mass contact. 

In the future you may consider using a module like Legal.