We make a detailed analysis of error mechanisms, gate fidelity, and scalability of proposals for quantum computation with neutral atoms in addressable (large lattice constant) optical lattices. We have identified possible limits to the size of quantum computations, arising in three-dimensional (3D) optical lattices from current limitations on the ability to perform single-qubit gates in parallel and in 2D lattices from constraints on laser power. Our results suggest that 3D arrays as large as 100×100×100 sites (i.e., ∼106 qubits) may be achievable, provided two-qubit gates can be performed with sufficiently high precision and degree of parallelizability. The parallelizability of long-range interaction-based two-qubit gates is qualitatively compared to that of collisional gates. Different methods of performing single-qubit gates are compared, and a lower bound of 1×10−5 is determined on the error rate for the error mechanisms affecting 133Cs in a blue-detuned lattice with Raman-transition-based single-qubit gates, given reasonable limits on experimental parameters.