We construct and analyze a microscopic model for insulating rock salt ordered double perovskites, with the chemical formula A$_2$BBO$_6$, where the B atom has a 4d$^1$ or 5d$^1$ electronic configuration and forms a face centered cubic (fcc) lattice. The combination of the triply-degenerate $t_{2g}$ orbital and strong spin-orbit coupling forms local quadruplets with an effective spin moment $j=3/2$. Moreover, due to strongly orbital-dependent exchange, the effective spins have substantial biquadratic and bicubic interactions (fourth and sixth order in the spins, respectively). This leads, at the mean field level, to three main phases: an unusual antiferromagnet with dominant octupolar order, a ferromagnetic phase with magnetization along the $[110]$ direction, and a non-magnetic but quadrupolar ordered phase, which is stabilized by thermal fluctuations and intermediate temperatures. All these phases have a two sublattice structure described by the ordering wavevector ${boldsymbol Q} =2pi (001)$. We consider quantum fluctuations and argue that in the regime of dominant antiferromagnetic exchange, a non-magnetic valence bond solid or quantum spin liquid state may be favored instead. Candidate quantum spin liquid states and their basic properties are described. We also address the effect of single-site anisotropy driven by lattice distortions. Existing and possible future experiments are discussed in light of these results.