I liked Yaser Abu-Mostafa's Caltech ML course. A bit dated (2012), but solid introduction to the basics (such as VC dimensions). However, given your stated preferences, other recommendations (such as fast.ai) are probably better suited.
I found this course pretty interesting, since it gives some perspective on what sorts of guarantees people want that DL doesn't provide, but I wouldn't necessarily recommend starting with it unless you have a theory bent.
https://work.caltech.edu/telecourse.html