Is this something I should do in the beginning stages of my site (when the map structure will probably still be tweaked) or should I wait until I have the final structure in a few months?
If your not going to drasticly change the structure of the site then submit one straight away, and update it as you site grows/changes. I thinks it help to show that your site is growing rather than the just submitting a site with lots of urls.
The Google XML site map can be generated for your website through the Webmaster tool. In that you may specify the likely changes that might happen on your site. I mean it will ask you whether the search engine crawlers will be notified after a week or a month or three months. So everytime you make changes on your website the crawlers are notified about the change. Then you may keep changing the website whenever you want and you may generate a sitemap easily and submit that on the root of your website. Let me know if this helps or if you still need any further assistance.
Updating & Adding Pages for a website is a continuous process. Hence you need not to wait so long to submit your sitemap to the search engines. http://www.xml-sitemaps.com/ this one will help you in creating a sitemap. [500 Urls is the Limit]. Don't forget to select your Changing Frequency Daily/Weekly/Monthly/etc. Create account on Google Webmaster Tools and submit your sitemap. Cheers!!!
Right now the home page is being changed quite often because I'm still working on the design. After I'm finished with the design, I'll update the home page every 2 weeks. But there is a subpage with my Classified ads that it updated daily. So what change frequency should I choose? Daily or weekly?