Brian,
Depending on your route, there is Petty's which is on Babcock just north of US 192 in Melbourne, but parking sucks if you're dragging a boat. There is Green Turtle on SR 518/Eau Gallie Blvd in Indian Harbor Beach just before A1A. Or for convienence, there is a Publix in South Melbourne Beach right on A1A about 10 miles north of Long Point with plenty of parking.
Of course, if you want FRESH tuna, you have to go 75 east of the inlet to the "otherside"
Lloyd