We present and analyze protocols for fault-tolerant quantum computing using color codes. To process these codes, no qubit movement is necessary; nearest-neighbor gates in two spatial dimensions suffices. Our focus is on the color codes defined by the 4.8.8 semiregular lattice, as they provide the best error protection per physical qubit among color codes. We present circuit-level schemes for extracting the error syndrome of these codes fault-tolerantly. We further present an integer-program-based decoding algorithm for identifying the most likely error given the (possibly faulty) syndrome. We simulated our syndrome extraction and decoding algorithms against three physically-motivated noise models using Monte Carlo methods, and used the simulations to estimate the corresponding accuracy thresholds for fault-tolerant quantum error correction. We also used a self-avoiding walk analysis to lower-bound the accuracy threshold for two of these noise models. We present two methods for fault-tolerantly computing with these codes. In the first, many of the operations are transversal and therefore spatially local if two-dimensional arrays of qubits are stacked atop each other. In the second, code deformation techniques are used so that all quantum processing is spatially local in just two dimensions. In both cases, the accuracy threshold for computation is comparable to that for error correction. Our analysis demonstrates that color codes perform slightly better than Kitaev's surface codes when circuit details are ignored. When these details are considered, we estimate that color codes achieve a threshold of 0.082(3)\%, which is higher than the threshold of $1.3 \times 10^{-5}$ achieved by concatenated coding schemes restricted to nearest-neighbor gates in two dimensions [Spedalieri and Roychowdhury, Quant.\ Inf.\ Comp.\ \textbf{9}, 666 (2009)] but lower than the threshold of $0.75\%$ to $1.1\%$ reported for the Kitaev codes subject to the same restrictions [Raussendorf and Harrington, Phys.\ Rev.\ Lett.\ \textbf{98}, 190504 (2007); Wang \etal, Phys. Rev. A \textbf{83}, 020302(R) (2011)]. Finally, because the behavior of our decoder's performance for two of the noise models we consider maps onto an order-disorder phase transition in the three-body random-bond Ising model in 2D and the corresponding random-plaquette gauge model in 3D, our results also answer the Nishimori conjecture for these models in the negative: the statistical-mechanical classical spin systems associated to the 4.8.8 color codes are counterintuitively more ordered at positive temperature than at zero temperature.