Yes! My favorite place is Nobu's in Malibu. I've tried a lot of places in the area, they win hands-down. You should have an easy time getting in on a Thursday (especially since you'll need an earlier reservation). Tiradito, black cod with miso (which I now have the recipe for), and yellowtail with jalapeno are among my fav dishes there. I've spent many hours there with friends.
It's not right ON the ocean, but it's just on the other side of PCH in the corner of Cross Creek shopping center. You and Stella will undoubtedly see some celebrities there. Phone number is (310) 317-9140.