Address a = new Address();
This creates a new instance of Address. It is not associated with a datacontext in any way.
db.StateProvinces.First();
This loads an instance of StateProvince. The instance is tracked by the datacontext that loaded it (db). db is waiting for notifications of changes from this instance.
a.StateProvince =
Here is assignment to a property. If you inspect the autogenerated property "StateProvince", you'll see that it also updates the related property "Addresses" on the StateProvince instance. Now the StateProvince instance has changed. This causes db to be notified, and as a result - the address instance is now tracked by db as a new, ready-to-insert instance.
The simplest way out of this is, before using db, set:
db.ObjectTrackingEnabled = false;
PS. var is awesome like hotdogs are awesome.