Cheapest address auto complete API?

I’m creating an application that use a key value store (Redis or Dynamo… but shouldn’t matter for this question) where they key is an address that maps to some info about that address…

I need a way to

A: Assist users in autocompletion of the addresses B: Normalize the address results (APT a104 vs apta104)

Another feature that would be nice is if the address retuned from the API gave a unique id per address, that way I wouldn’t have to come up with my own encoding scheme to map addresses to keys… I’m still considering doing that anyway, but it would be a nice thing to have.

Which API would you recommend here? The Google APIs are a nice starting point, but I hear they are quite expensive. I don’t want to have to rewrite with a different API down the road.

I am also bootstrapping this app with my own money and won’t have any monetization up front… so I’m very cost sensitive.

There are a handful of APIs I could use here… Can anyone share some hands on experience?

One other idea (I dunno if this exists) but if there is a way to get a dump of these addresses so I can host them myself… that could be an acceptable alternative. I’m currently only operating on the scale of a single USA state, and it’s acceptable if the addresses are bit stale. Updating them once a month or so in batch would suffice.

Thanks!