Lattice artifacts in the 2d O(n) non-linear sigma-model are expected to be of the form O(a^2), and hence it was (when first observed) disturbing that some quantities in the O(3) model with various actions show parametrically stronger cutoff dependence, apparently O(a), up to very large correlation lengths. In a previous letter we described the solution to this puzzle. Based on the conventional framework of Symanziks effective action, we showed that there are logarithmic corrections to the O(a^2) artifacts which are especially large, (ln(a))^3, for n=3 and that such artifacts are consistent with the data. In this paper we supply the technical details of this computation. Results of Monte Carlo simulations using various lattice actions for O(3) and O(4) are also presented.