Southern California has a variety of Spanish restaurants, but I suggest that one checks the menu prior to making plans, as there are still some morons running restaurants that think "Mexican" and "Spanish" are synonyms.
Of the few I've visted, these are they:
Viva Madrid, a tapas bar located in quaint downtown Claremont, off the 10 fwy at Indian Hill Blvd., the ambience is fantastic, and all the items on the wall [an eclectic mix] are for sale...just ask.
Cafe Sevilla, Riverside [and other locations]. Not fully Spanish, more of a fusion place. Paella was not traditional, but had a few good tapas on the menu.
Luna Negra, Pasadena. Just south of Colorado Blvd., great ambience, but ever since MissMadrid98 left, there hasn't been a flamenco show like they used to have!
Food was good, small portions and a bit pricey.
Cafe Madrid, San Diego. Good tortilla. 'Nuff said.
...and my personal fave:
Centro Basco in Chino, south of the 60 on Central Ave. If you like lamb, traditional family-style eating, and good portions for the price, you're in the right place. I'm not biased, either. I took a colleague to lunch here and he suggested that all subsequent lunch meetings be in the same place.