Oof, Cali from Texas-- quite a change! The California horse world can get much more expensive than other areas, so brace yourself 
I recently graduated from UC Davis and rode at a couple of places in Yolo County. I live in Sonoma County now (wine country prices are OUCH, but I digress) and I adore my current place. There are some lesson horses at the first two I list below.
Alana Curtis @ SunFire Eventing Center, Woodland CA – bought my horse from her and rode with her while I was in college. She’s lovely. $60 private lesson on a school horse. http://sunfireequestrian.com/
Toora Nolan @ Santa Rosa Equestrian Center, Santa Rosa CA – currently ride/board here and the facility is stunning, Toora is awesome and there are other trainers on site. Lots of horses for lessons/lease as the facility houses over 100. Toora runs $55 I think for private lessons on a school horse. http://srequestrian.com/toora-nolan.htm
Holly Fox @ Fox Farms, Davis CA – I have never ridden personally with her but I have a friend or two who like her. Unfortunately I cannot say re:lesson horses and prices, but she’s accessible through email. http://www.foxfarms.com/
I don’t know where exactly you are but there are 3 (potentially…) driving distance from Solano. Hope this helps, and best of luck finding something 