There is a reason why it is not so easy to find such a data. Each state has its own rules for operating data like that. Most data out there comes from elections and can be floating around for dirt cheap if it is old.
Whoever, be very careful if you decide to use such data. It comes heavy regulated. See voter list regulations.
Another source could be geocoding databases/census data. Each state again is listed separately.
Third option is to buy consumer data. It has much more than just addresses. and price is not cheap as you said.
I am a data vendor myself and sell voter and consumer data. However, I am very skeptical when someone ask for huge amount of data for personal use.
The amount of data is very hard to operate if you are not technical enough as the volumes are big. Databases require maintenance and the most important thing: data gets old the day you obtain it.
So, eventually when you buy old data, if you planing to send bulk mail, you will waste much more for invalid addresses than buying the right data for initial higher price.
Disclaimer: I founded Batch Geocoding platform CSV2GEO and Voter/Consumer online data Walk Lists.