This all sounds like it would make an interesting blogpost/article if you're into writing one.
The best change I made was having them first enter zip code, then pick city/state from a list that goes with that zip code. Both Google and the USPS have apis for that mapping.
Also, fun fact: UPS charges me $15 if they have to make an address correction at delivery time. So, for example, if a customer fails to put a Suite number in, and the UPS software doesn't tell me it's missing, UPS charges me $15. I've complained that I shouldn't have to pay when their software fails. They don't care. Argh!