There's a traditional California style barbecue which sort of came out of the central coastal valleys. A lot of people call it "Santa Maria" style.
Tri-tip or top block sirloin are the main meats -- although you can add other things if you want. Ideally, they aren't smoked in a smoker, but cooked open pit over a bed of live oak coals. Most people don't have pits or grills which can handle a fire made from pieces of wood large enough to make coals, but you can certainly use a good hardwood lump charcoal (like Lazzeri Mesquite or Oak), or a mix of hardwood lump charcoal and some actual hardwood lumps.
Most people don't have the kinds of grills which allow you to raise the grate high enough to deal with the vagaries of a fresh coals from wood fire either. But that's not a big issue anymore either. The trick -- and it isn't that much of a trick since the birth of good covered grills like Webbers -- is to get a good sear on the outside, then finish cooking the tri tips over indirect heat or high enough above a live fire that the outside doesn't turn to coal while the inside moves to medium rare.
Beans -- but "frijoles de la olla," not baked beans, and not "chili beans" either -- are one of the traditional garnishes. I love baked beans but with tri, regular beans are just so California. The big deal tradition from the central coastal valleys is pinquito beans, but pintos will do fine.
Other very traditional garnishes -- traditional to the point of being mandatory -- are a simple salsa like your pico de gallo; sourdough bread done as garlic bread; and a simple, retro (no candied walnuts!), green salad, like Caesar, Green Goddess, etc.
The coastal valleys saw some eclectic immigration before WW II, and you see some things you might not think of as California, American or even barbecue. For instance, in the Santa Ynez Valley around Solvang you often see Danish style cucumber salad; it's not uncommon to see Portuguese linguica in some of the other valleys; Santa Barbara waters are known for shrimp (which do pretty darn well on the grill); no meal of this sort can go wrong with one sort of artichoke dish or another; and avocado, whether as guacamole or in some other way, won't make you any enemies, either; and, well, you get the picture.
Your grilled zucchini would work very indeed. So would a warm "Mediterranean style" salad made from a variety of grilled vegetables -- say zucchini, onion, eggplant, peppers, and tomatoes.
People from the south might say it's "grlling" and not "barbecue," but we Californians know better. It's how we do.
It sounds like you're already three-quarters of the way there. So, wotthehell wotthehell, might as well go all the way.
If any of this sounds good, let me know if you'd like assistance with specific techniques, rubs, recipes or whatever. It's one of my favorite styles of cooking, and I'd love to help.
PS. Go Cal!
Edited by boar_d_laze - 9/2/10 at 2:06pm