I am wondering if it is possible to create about 3 different design templates, and have the front end users choose which ones they would like to use. E.g., if we have different departments that each have a site, is it possible to let them choose from a few different color schemes?
Yes, you can do this.
Create your designs and add them to the sites a user defined designs (on the settings screen) in the same way you would for a printer friendly design. The one you make the default frontend design will be the default. The others can be accessed in the same way as the printer friendly design.
Let's say you have designs with codes design1, design2, and design3. In the parse file for design one, put this somewhere:
SQ_DESIGN_NAME=design2&SQ_ACTION=set_design_name" title="Set Design 2">Switch to design 2 SQ_DESIGN_NAME=design3&SQ_ACTION=set_design_name" title="Set Design 3">Switch to design 3
Then in the other designs, do the same thing but switch the design codes around.
When the user clicks on one of these links, Matrix will display the page with the other design, and will set it to remain used for the rest of the session.
But doing it this way, can I have users set a specific design as their default, and have that default design come up for all public, and private users, until they change it to another design? So that it would not only be up until their session is over, but for as long as they want, until they change it?
I think you're confusing frontend users with backend users here. If you want, you can allow your backend users the ability to change the default frontend design on the assets to which they have admin permission. Then, that design will be used for everyone who views the site.