Another thought; what if Canals were made to be small wonders. Everytime you wanted to build a canal, you'd have the city nearby where it is to be built, build the small wonder "(name of city) canal" The # of squares this canal will bridge will determine it's cost (50 or 100 shields per square, perhaps.) Then, once the small wonder is build the canal appears along he shortest route between the 2 locations as well as slong the path of least reistance (not through mountain; although it might go throug hills if it were cheaper (hills would cost 150% more per tile than would plains,grassland desert. Forests would coust 125%, but you'd get the shield bonus when they're cleared.)
Once you build the canal you have a new diplomatic option: grant usage. With this you can choose which civs can choose which canals and for how long (10 turns, 20, ect...)
Any thoughts?