I have gone riding at the beach before, in fact when I was on a vacation I took a few trail rides at the beach, and on the final one I got the chance to ride this big huge Belgian Draft gelding (per my special request) and gallop him down the shoreline. It was a lot of fun!
I know there are a lot of beaches, just like parks and other public places, that will allow horses. You would need to call around locally to find out more, but I'm sure you could find lots of places for this.
Your experience will entirely vary of course depending on you, your horse, and how you approach the situation. I would give you a few words of advice before you go out to the beach with your horse. First of all, you may want to make sure your horse has a lot of experience out of the arena. Trail rides and exposure to anything he may find scary on or near the beach, such as traffic, bicyclists, crowds of people...even beachballs, umbrellas or brightly coloured beach chairs/towels could be scary!
It's best to go out on trails, and especially to the beach, with other riders. If your horse is known to be spooky or nervous, it can help to have someone ride with you on a more experienced, calmer horse. Go prepared with enough water, a first aid kit, a cell phone and anything else you may need, especially if you do end up riding alone. Lastly, it could be a good idea to lead your horse around the beach before you get on and ride. That way you can judge his reaction without risking a fall/bolt and keeping both you and him much safer.