a. You can use parking / traffic data to find neighborhoods most likely to have available street parking and look for parking there.
As for solving the problem of when you're allowed to park somewhere, this is already being worked on [0][1] and I would put money on it being ready before autonomous cars.
b. Use parking garage app to find the best balance between distance and price of parking for the time needed.
As far as determining if the garage is full, many garages have sensors now that count how many open spaces there are. It would not be stretch to assume that by the time autonomous cars are ready, this data will be available within the parking apps.
c. One of the cool things about having a computer make these decisions is that it can factor in a limitless amount of data to make the most efficient decision. Kind of how Google Maps gives you different transportation options when you ask for directions, you could do the same with parking.
The car can ask you, which of these options would you like:
1. Drive 30 minutes in this direction and you can park for free. Cost for power to drive there: $1.12 - Time to summon: 30 minutes - Cost for parking: $0.00
2. Park in a parking lot around the block: Cost for power to drive there: $0.08 - Time to summon: 5 minutes - Cost for parking: $10.00
etc...
I agree with you though, parking is a huge issue in the city and I really can't believe it hasn't been fixed yet. We are getting there, but very slowly.
[0] http://sfpark.org
[1] http://spotangels.com