I think "Artificial Intelligence a Modern Approach" is still the best foundation book. However it certainly is not focused on deep learning. There's chapters on pretty much everything (one on reinforcement learning) but it is build around the idea of intelligent agents first and foremost. Best written CS book I own.
I think this book is actually very approachable without much of a mathematics background. It's structured so that you can usually skip the mathy parts (and there aren't many really). Time and space complexity might be a bit tough but it's not that hard to work through. I think the Bayes related math was explained well and should be approachable with next to no math knowledge.
The math is mostly applied and not proofs. There's a fair amount of pseudocode and algorithms but they are explained well and I think it's not hard to follow (our students of different backgrounds usually didn't have problems). I did get a bit tired of the running example of the map of Romania (essentially used for all the search related things).
The diagrams for algorithms are very helpful.