Rather than buying the Garmin maps for my Edge 800, I decided to give OSM a try. You just need a micro SD card to put them on. The Garmin 800 connects to computer as a USB 1 device so file transfers are extremely slow. For a large map it is better to use a card reader to transfer the file. The maps from here are updated about every week: http://www.osmmaps.com/ . This site has a good set of instructions for installing the maps: http://ridewithgps.com/help/garmin-edge-800
The OSM maps are only as good as the mappers in your area have made them. Fortunately since anyone can edit the map that is something you can help with. For an area that has been thoroughly mapped, the biggest difference between the Garmin and OSM maps is the meta data. Garmin's maps include a huge database of zip/postal codes, street addressing and business / attraction names. The OSM maps typically have none of that aside from businesses and places that have specifically drawn on the map.
When riding a route discrepancies between the OSM map, map used to create the tcx course, and reality can cause it some confusion. Where the two maps cross each other it thinks there is an intersection so you can get annoying phantom turn instructions. Most of the ride mapping sites seem to use Google's maps. Garmin Connect does have the option of generating a course based on OSM data, so it would eliminate the discrepancy between the route and on board map.
During the fall I did a lot of rural road riding where I noticed the maps near me were very incomplete outside the city. I contemplated getting the Garmin maps, but instead decided to start editing the OSM maps. Since I was making so many updates I didn't want to keep downloading a huge map file for the entire country. I found out I could generate my own map for my province current as of 4pm the previous day. If anyone is interested I could put together instructions for generating maps as the OSM documentation is somewhat convoluted.
OSM has a web browser based editor for making changes to the map and I recommend giving it a try. But their downloadable program JOSM is much more powerful. The web editor is limited to drawing roads, but JOSM lets you open data files an copy / paste in new roads. For Canada the government has made available OSM compatible geographic files for the entire country. Adding alleys manually to my own city took two weeks. Using the data files to add alleys to a larger city took a day. And adding all rural roads to an area of about 270,000 square km took 3 weeks.
You can also use the gpx files from your rides to help spot areas where roads are missing. I did this to add new sections of MUP that don't even appear in the satellite imagery yet. Also to add those little paved paths that run between houses providing pedestrians access to parallel roads without going to the end of the block.
I had OSM issues where some roads were not routable or some were erroneously characterized as one-way. Also, I frequently get totally wacky turn prompt diagrams. An upside of OSMs was that routes calculated about twice as fast as with Garmin maps.
One thing that is important for routing is that roads don't simple cross each other but they are connected. In the past few weeks I also came across a few roads where people tried to trace numerous roads in the satellite pics in a single continuous line that crossed and overlapped itself. There is a web service called Map Roulette that tries to detect connectivity errors and randomly presents them to users of the site for correction. So things should get better over time if you periodically download new maps.