My first response is always, NO FISH
but after that there are a few interesting critters that work.
Pretty much any brittle star (greens can get aggressive and may be a concern for smaller octos) or serpent star is fine and will help keep the tank clean. We always keep a
red brittle in with the octos (and they are all named Pesky) as they seem to hang out with them and sometimes make it easier to locate a new den. Most brittles and serpents can be taught to be hand fed but you will not see them often (except at feeding time). The red brittles (actually more of an orange) add some nice color and are sometimes out during the day. Another attractive serpent star is the
harlequin (black and white and sometimes green and white striped) but they are very reclusive and ONLY come out at feeding time.
I also like to keep
knobby stars as they eat a lot of the scraps and seem to do very well in the octo tanks. They stay out during the day and can be very brightly colored.
Pencil urchins are octo safe and will help keep the algae on the rocks minimized (this includes the purple coraline algae though and I would not recommend them if you like a lot of coraline on the rock work). They are likely to chew on softies and gorgonians as they age if there is not enough algae in the tank for them and I have had to move several. I end up putting them back in though when the rocks need cleaning.
You can keep most gorgonians in the tank but you will need to take care to locate them in continuous current, good lighting and not in a likely octopus path (you will note that your octo does NOT go around things) for survival.
Most any mushroom (excluding ricordeas) or soft leather coral is fine but again, keep in mind the octopus habit of crawling over not around and you will need to establish them on a substrate before adding them to the tank.
We have had several peppermint shrimp to survive octopuses BUT the shrimp really need to be introduced before the octopus and even then some are not fast enough to survive so it is hit or miss with them becoming food. Small hermit crabs will also sometimes survive once an octopus is accustomed to being fed. Often a newly introduced animal will eat snails and hermits but leave them alone after it accepts the easier hand fed foods. However, there are exceptions. My vulgaris ate anything she could find in the tank in addition to her daily meal.
You want to avoid anything that has a strong sting so most zoanthids are not recommended (keep in mind that stinging cells can be set off in the water and your tank is not the ocean so they will remain for a period of time and can cause irritation that may lead to infection and a
recent incident points out the toxicity of some zoas). I have found one group of larger polyps that seem to do fine and recommend that if you try any you keep them contained to a removable rock and relocate the rock to another tank if the octopus reacts to touching them.