How to change date format
Email: firstname.lastname@example.org or email@example.com
English (United States) will give you mm/dd/yyyy date format. English (Canada) and French (Canada) will show dd/mm/yyyyy.
Here's a link from the help files that shows the date and number formats for the Locales.
At our company, I find the typical Canadian compromise - there's no consistency with date formats. Depending on the originating system, I see date formats of mm/dd/yyyy, dd/mm/yyyy or yyyy/mm/dd. Personally, I like yyyy/mm/dd because I don't have to wonder if 05/06/2012 is May 6 or June 5, but salesforce doesn't offer that option
As for changing the user's Locale between the English Canada and English US, it really only affects the date format. Selecting a European Locale can affect the meaing of a "week". I actually had to move a team to English Ireland just because they wanted a week to be Monday to Sunday instead of Sunday to Saturday.
You can use the Data Loader or Excel Connector to change all of your users to a specific Locale.