We feed ours live cancer crabs (Cancer novaezelandiae ) and paddle (swimming crabs) (Ovalipes catharus ) Plus the occasional giant spider crab (Jaquinotia edwardsii ) which was purely unintentional The octi crawled into the tank and helped itself!
I go up to the local bait and tackle store and buy two dozen bait shrimp for about $3.50. Their average size is about 2" long, and I've gotten ones as big as 4.5" long. I also have silversides in my freezer for treats.
never owned an octo myself but a guy at the lfs had a blue-ring (naughty naughty i know) and he fed it anything he could collect from the beach or dives - mainly pipis cos they are so easy to store!!! (big box of wet beach sand- make sure to wash them first cos the beach sand can be dodgy!) and other small shellfish but also live sw feeders and small crabs he could catch!!!
When the octopi I've taken care of were young, I generally fed them small shore crabs found around some of the docks where I live, and occasionally a chopped up piece of fish/squid. (Some don't like the dead stuff as well, unfortunately) The older ones always like live crabs, of course, but I have one now that is peculiar and will gladly go for mussels. Which is excellent, since live crabs are hard to come by this time of year...
I buy about 300 fiddlers from the bait shop when they are in season for $5 the lfs sells 2 fiddlers for $5 I keep them in one of those rubermaid containers with a fluval 4 in it and those floor buffing pads so the crabs could hang out on above the water
when I run out of fiddlers and they are out of season I feed my bimac frozen shrimp from the market with a feeding stick
My last bimac even took a big blue crab from the fish market killed it but when it couldnt drag the crab into its den the octo left it I took the rest of the crabs stuck them in the freezer and broke them in pieces about a quarter of the crab was given every day