The haze will be an issue no matter what; that's a fact of this area. The way to "fix" that is to shoot in the winter when the air is colder and crisper, especially just after a front moves through and clears it out. That's when you'll get interesting/dramatic clouds as well. Summer months are just not good for landscape vistas in the bay area. I don't even consider shooting the kind of shots you're thinking of half the year, only between about October and March, unless a rare front moves through
Also look to shoot early on days with limits or no marine layer, winter or summer. There's some wonderfully dramatic cloud formations that show up in the winter if you're awake and in position to take advantage of them in winter (which means being in position by 5:30AM or so.. yawn).
A couple of areas to keep in mind. There's a vista point on Skyline (highway 35) that looks to be useful for an east facing vista of the bay; I scouted it a while back but haven't gotten back there to shoot. Should be interesting both dawn and pre-sunset when the east bay hills are lit and the rest is shadowed -- if there's decent cloud work and little haze. I don't have my notes handy, but I believe it's N of 84 along the way up to 92. That's a wide swath of road but it'll be obvious when you hit it. room for 6-8 cars.
There are some photo opportunities from the east bay hills on Calaveras out behind Ed Levin Park in Milpitas. No perfect place -- some utlity wire obscuration and no great parking spot -- but you might find some decent shots there.
I've also wanted to explore the campus at CSU east bay (hayward); there seems to be some real opportunity for shooting from that campus, but I haven't been there in years so I can't suggest more than go and look.
