Map behaviour populating with List

When you add a record to a collection (or, in your case, use one collection to build another), what you're doing is making references to the original records.

Because they are references, when you change a field value on one reference, you end up changing the field value on all of them.

To 'break' the references so that your old and new maps are independent of each other, you'll need to clone the records (which creates a completely separate instance of the record(s), in memory).

The following will work as you are expecting:

// Query for a List of Accounts
List<Account> accountList = [SELECT Id, BillingStreet, BillingCity, BillingState, BillingPostalCode, BillingCountry FROM Account];

// Create 2 maps. One for old versions of records, one for new.
// I didn't see any reason to avoid populating old map at initialization, so that's
//   what I'm doing.
Map<Id, Account> oldAccMap = new Map<Id, Account>(accountList);
// Instead of initializing the new map with an empty map, let's deepClone() the old map.
// This will create clones of all of the records held in the old map
Map<Id, Account> newAccMap = oldAccMap.deepClone();

// Now you're free to change field values on records in one map, and it will not
//   affect the corresponding record in the other map.

+edit:

Now that I'm fully awake, and took a second look at this, I suppose I should elaborate a little more. Cloning isn't the only way to make a new in-memory instance of an object (or collection of objects). As you discovered yourself, each query returns a new, independent collection of records. Using the new keyword (a la new Account();) also creates a new in-memory instance of an object.

In this situation, cloning happens to be the easiest (and fastest) way to accomplish what you're looking to do (it also saves a precious query, which makes it an automatic 'yes' for me in pretty much every case).

One thing to look out for is that maintaining multiple instances of an object in memory takes up more heap space than one instance + many references do. There is a governor limit on heap usage, but I myself have never run into it. If you run into heap issues, but need independent instances, I think the only solution would be to split things into separate transactions (batch/queueable).