Since you are seeing nitrates and algae growth, I would go ahead and start a 2 week water change program. After you have your critter, once a week is advisable. Nitrates will continue to build as your tank cycles and continue after as it ages if you do not do maintenance. After the tank is established, climbing nitrates are a sign that you need to do heavier water changes, they will never decrease without maintenance. Nitrates are, however, a sign that your tank is cycling well at the moment. One thing that is not well written and I try to emphasize is that a water change is more then just swapping old saltwater for new water. It is important to disrupt the tank a bit and stir up the bottom substrate as well as squirt down the LR to put the decay into the water column to be removed both by the water change and whatever filtration you are using. I like to take a bamboo stick and stir the sand where I place my siphon so that I get a lot of the cloudy water as I disrupt he substrate.
I agree with bluespotocto, if you can find a couple of serpents, they are one of the very best clean up crew for an octo tank. There is also a diurnal star commonly called a thorny star that is often a brilliant orange and has been a mainstay of my octo clean-up crew (they are not reef safe for corals, however, and should not be kept with anything more than polyps). They are particularly attractive, active and attentive to left overs. I avoid all fish, either they will pick on the octo or become lunch. Lunch is not so bad but even in the wild they will annoy an octo while eating (the only one I have seen in the wild be being harrassed by a wrasse and is why the octo was detected) or worse, pick on the octo. Yours in particular will not be in the best of health to start with so minimizing stress is important.
If you can find a nice looking leather coral, they are hardy, usually survive a young tank and add some dimension. Any mushoroom seems to be acceptable, the red ones I use from the Caribbean do particularly well in lower lighting. They don't multiply but do get large. Polyps (zoeanthids) are touchy. They have varying degrees of stinging cells and octopuses are sensative to the sting of most. I have some that are brown and white (the solid browns I have tried had to be removed as the octo definitely reacted) that are commonly called sun polyps (not to be confused with the hard coral by the same common name). In general if you put in zoes, look for very short tentacles and watch for a reaction from an octopus. It it touches the polyp and acts like it is hot to the touch, remove it.
Sponges are another piece of color but need to be monitored and removed quickly if they start to die. Most are not a huge water problem but some can poison the water at death (one commonly called a red ball sponge is know for this unfortunate property). Red or orange "tree" sponges seem to be safe even if they die off.
Gorgonians don't tend to be a problem but need a delicate balance of current and to be placed where an octopus won't be constantly disrupting it.
No anemones. They sting and can even eat a small or unhealthy octopus. I love flower anemones but they are kept in different tanks. I found one of my flowers trying to eat one of my antler anemones the other day and was totally surprised. I was able to extract the antler from the mouth of the flower and everyone is fine (in diffrent tanks!).
I am really looking forward to seeing how this experiment will work out and I hope your wife is starting to enjoy the tank.