Given its societal impacts and applications to numerous fields, machine learning (ML) is an important topic to understand for many students outside of computer science and statistics. However, machine-learning education research is nascent, and research on this subject for non-majors thus far has only focused on curricula and courseware. We interviewed 10 instructors of ML courses for non-majors, inquiring as to what their students find both easy and difficult about machine learning. While ML has a reputation for having algorithms that are difficult to understand, in practice our participating instructors reported that it was not the algorithms that were difficult to teach, but the higher-level design decisions. We found that the learning goals that participants described as hard to teach were consistent with higher levels of the Structure of Observed Learning Outcomes (SOLO) taxonomy, such as making design decisions and comparing/contrasting models. We also found that the learning goals that were described as easy to teach, such as following the steps of particular algorithms, were consistent with the lower levels of the SOLO taxonomy. Realizing that higher-SOLO learning goals are more difficult to teach is useful for informing course design, public outreach, and the design of educational tools for teaching ML.