What edition of the CD are you getting with the car? My 2008 version CD shows all of Canada - no problem finding my way around Edmonton....
There are updated CD versions, even though the cars in the meantime do have DVD - as you correctly state. So for your 2003 car, simply get the latest CD release and you should have no problems. I just saw a Feb 09 Canada CD on eBay....its whatever one came with the car im assuming, so its from 03. but isnt 04 and up dvd based? and the 03 doesnt have dvd right?