Some of the cost could be mitigated with "toll-free" options, such as using a vehicle tracker like EZ-pass and not charging you if you travel less than N miles (to encourage people to live near work), or giving partial refunds if you use your car very little during a month.
Another option could be a centralized "smart-driving" app, that would act as a hybrid between self-driving and manual driven cars. Each driver could be given "hints"/instructions, and measured on their compliance rate. The reward would be a measurable improvement in travel time. For instance, if 80% of the cars on a block were using this app, preference could be given to hold a signal light green longer for them. Drivers would see a benefit, and that would be their only impetus to comply with its directions (slow down, turn left here, park and wait 5m, etc). Someone who never listened to the thing would be kicked off. Soon with enough users , you could organize mini "convoys" of cars travelling through the city (say, all cars slow from 65 to 60mph for 2 miles, so that the offramp signal could be ready and green at the exact moment of their arrival and kept green for the whole convoy) and attempt to optimize travel for them or give them other perks such as free parking. It wouldn't solve all problems, but it would encourage cooperative behavior on the roads which may go a long way to easing congestion.