Julia,
A 65-70 rectangle (vs cube) with a 20-30 gallon sump is a nice size for O. briareus but O. vulgaris can be a challenge. Caribbean vulgaris are typically smaller than their Mediterranean cousins but are still heaftier than O. briareus (with roughly the same or even slightly shorter arm span). I have kept an O. vulgaris in a 65 with a 35 sump and was lucky that
LittleBit did not outgrow her tank. I did have an alternative if she was more typically sized but never had to octo-proof the 140 for her. Linda's,
El Diablo, on the other hand needed a much larger environment.
Sorry but if you want a brightly colored tank, then an octopus won't be your creature for this tank. You are pretty much confined to a species only tank and very few other animals. Most clean-up crews are either quite dull (in coloration, not necessarily in activity) and other critters can either harm the octopus or visa versa. I don't find my tanks boring even without an octo in residence but most marine enthusiasts are not fond to the "pile of rocks" style that decorate my rooms.
Here is a list of tankmates CaptFish and I put together as suggestions. Note the article at the top of the thread of animals that did not work.
If you have your heart set on a ceph, have a look at cuttlefish. They can tolerate a wider variety of animal life (not fish, but corals), are somewhat easier to keep, can be grown from eggs so you will have a longer period of time with them (octopuses, for all intents and purposes are wild caught and half grown when they arrive at best) and there is a possibility of mating a pair to propagate an additional generation. Feeding new hatchlings gets quite expensive but once they accept frozen foods, the cost is similar to keeping an octopus. You still have to take care with what corals you can have but since most swim instead of crawling, you have more color options.