Changing Address Format

I have been looking through the AddressAdd & AddressEdit view files and trying to figure out how to change the address format from the current to the below format.

Address 1
Address 2
City
State
Zip Code
Country

Has anyone changed the layout of these fields, and if so can you point me where to do so?

The problem with putting Country last is that the State drop down is dependent on the Country selection.  It could be confusing for the customer.