The best start I ever had to Artificial Intelligence was via UC Berkeley's CS188 course[1]. This course takes you through the very foundations of AI, from search to planning to basic probability theory. It's been imitated at universities around the world with its open lectures, slides, homework assignments and project code.
The projects are the very best part of this course. You start with a blank slate PacMan agent trying to pick up dots to something able to track & dodge ghosts without even seeing them (!). It's what inspired me to continue AI research 7 years down the road!
[1]: http://inst.eecs.berkeley.edu/~cs188/fa11/lectures.html