Simple way to export your customers from Magento with their address.
In the ADMIN on the menu select
System -> Import/Export -> Dataflow Profiles.
Select customer on the dropdown then go to the run profile tab and click go.
It'll save it on your server in the /var/exports/ folder.
By default this will come out with their billing address.
Yep, that simple.