I would enjoy coming across a rare resource on the map that would lower the cost of improvements and training in the city it is linked with.  I was thinking it would make sense for this to be a fuel source, like coal maybe.  The trade off of using this resource would be lowered prestige in the city that uses it.  Burn lots of coal, things get a bit automated and cheaper, but your city is filled with coal dust and soot and people are less likely to move in. 

Or, perhaps instead of making things cost less, coal could slightly increase the yeild of other resources in the city, maybe raising the output on farms, mines, lumbermills, etc, by 10% or so. 

Another way this could be implemented would be to have a improvement like a charcoal maker that creates a fuel source for that city at the cost of one material per turn (like a house costs one food).  It could operate the same way, either boosting output of other resources, or making things cheaper to train/build in the city, with the penalty of reduced prestige.

My final idea for the implementation of a fuel source would be to have it be storable like a regular resource that can be spent to finish things that are being built/trained.  If you've played Master of Magic you probably remember how you could spend a huge amount of gold to have a building be built in one turn.  Maybe this resource could be used in that fashion.