Over time I've changed my advice on tankmates, due to both experience and learning more from reading.
I tried a pencil urchin (you can't choose any urchin with sharp spiines). This worked out well, but after the first year of being in the tank, the urchin was large and begain to seriously eat my coralline algae. Then I read that such an urchin needed a 200 gallon tank so as not to deplete the coralline algae.
Starfish are difficult to keep and don't seem to thrive in our tanks.
Brittlestars can be quite good, as long as you avoid the large green brittle star (serpent star).
Snails and small hermits are good - you octo may eat them when he's young, but later prefers other food.
Some people have tried peppermint shrimp and in certain cases the octo considers them tankmates and does not eat them. I sometimes put 25 small shore shrimp into the tank - one or two didn't get eaten. They lived for a long time, were cute and could be hand fed, and were wonderful scavengers.
Fish are not good. Clams will be eaten. Nudibranches, sea hares, sea slugs, etc. are to be avoided.
Mushrooms are good, but remember that an adult octo, especially a large one, may romp through the tank and then create a den - and nothing is sacred. However, mushrooms like out of the way places, so it's worth trying. As for featherdusters, octos have been known to snap off large featherdusters and stick them in front of their den entrances. Clumps of small featherdusters might survive.
Don't forget the value of brightly colored shells. If you use those, you might not need so many tank mates. Also, after experiencing den-building, I'd highly recommend having a bunch of lighter material like shells in the tank, otherwise your female octopus will be heaving 10 lb pieces of live rock about (and believe me, they can do it!)
Of course, like it or not, you'll probably have bristle worms!
Any one else have good experinces with other sorts of tankmates?
Megas Always liked to chase his pet domino damsel around but i think that was a "special" relationship not to be attmepted.
Zim always liked the cat
but zim was a cuttle and they might have differing tastes.
About corals - octos don't need (or like) bright lights, plus their tank needs to be closed to prevent escape. Both of these factors make it difficult to keep corals - no metal halides, no open top. Also, you can't keep any coral that stings - an octopus's skin is very sensitive. On an actual reef, an octopus can avoid these types of corals.
Now you might be able to get away with mushrooms and a little piece of something like leather coral.
Octopus don't do too well with most tankmates...there are exceptions to every rule, of course...but, mostly, they are a species only type of animal in captivity.
You can try almost everything, but, be prepared to lose it.
soft corals will grow under the worst lighting conditions... in my 125 octo tank ive got several toadstools and other leathers along with lots and lots of mushrooms. my lighting is only 2 48 inch standard aquarium lights with vhos in them... the vhos dont burn as bright as they do on a vho ballast but they are slightly brighter than a normal bulb. the tank isnt bright at all though cause of the depth. the corals actually are growing better in there than in my 50 reef under a 250 watt metal halide. so in conclusion you can put leathers in and mushrooms.
i also had 2 pj cardnal fish in the tank with ahab and they were too fast for her to catch(way too fast, like no chance in hell) but they never even looked at her even though they are primarily nocturnal also. the cardnals and the octos occupy two different water territories, the cardnals stay in the open upper water while the octo stayed towards the rockwork and bottom