Can I force deploy a custom template and color palette to all PowerPoint users on Mac's and PC's?

I would put custom colors into a color theme (if the colors will be applied to Excel or Word documents) or in the presentation theme if they will only be used in PowerPoint. If you have up to 10 colors, you can use PowerPoint to create the colors theme. If you have more than 10 colors, please see my tutorial at XML Hacking: Custom Colors to add extra colors to the palette.

BTW, if your users are on earlier versions of Office than you, you must test your files on those earlier versions before distributing them. New versions can always open files from older versions, but the reverse is not always true.

Steve Rindsberg's page tells you how to set a presentation as the default: Create your own default presentation

When I have multiple files, I create an installer using PowerPoint VBA. The advantage to creating an Office installer using an Office program is that it's easy to find the locations on any computer for the templates and chart templates, even if they've been customized by the user. However, creating such an installer from scratch is not a trivial task, so I reserve that for the big clients with deep pockets. Without using an installer, you'll need to write comprehensive installation instructions that include file locations for all the different versions your users are on.