Little did I know that the Canadian government makes a complete survey of this information available under an extremely non-restrictive license (basically all you need to do is provide attribution). One better, they've come to an arrangement with the OpenStreetMap project that allows them to import all this data (under the creative commons attribution license), which will (as long as some care is taken) bring OpenStreetMap up to the level of Yahoo or Google maps. I'm positively giddy about the novel applications this should make possible.
That being said, integration of the data into OpenStreetMap will probably take some time. However, if you're writing an application which consumes OSM data (like I am), there's no need to wait. All I had to do to get an extremely accurate and complete OSM file for the region of the Halifax Regional Municipality was download the Nova Scotia road network in KML and use gpsbabel to simplify and trim said network down to my region of interest, outputting the result in OpenStreetMap format:
gpsbabel -i kml -f RoadSegment.kml -x simplify,error=0.01k \ -x polygon,file=restrictpoly.arc -o osm -F hrm.osm
The result? Pure city road network win. Here's a quick visualization courtesy of a cheesy 100 line script I knocked up using PyGame:
The empty space in the middle is the Bedford basin. The dense structure towards the center is the Halifax peninsula, connected via two bridges to the city of Dartmouth. The cluster to the north is Bedford.
I'd like to emphasize that, internally, this is a complete map, with street names and everything. Apparently GeoBase also provides a data set with address information which could be useful for writing a free geocoder, but I haven't had the chance to look at that yet.
If all that was nerd speak to you, just wait. I'll be bringing this topic down to earth in a way that any conscious being can appreciate in a few weeks...