Courses that give good insight on the nature of a Computer Science major?
Here are some thoughts about your suggestions for further study, plus one that you didn't mention.

Discrete Mathematics

This course should be part of the background for every computer scientist. The material is relevant for lots of areas we deal with and can be interesting and engaging whether or not one is going to concentrate on CS. That said, though, the subject matter won't necessarily give you an insight into what CS is really about unless it is specifically tailored to computer science applications (which it rarely is, in my experience).

Theory of Computation

A great choice, though it takes a bit of "mathematical maturity" to get through (meaning that you might find Discrete listed as a prerequisite). In one sense, this is the foundation for much of the rest of CS, since it asks "What things can and cannot be computed?" and often proceeds to answer this question by looking at increasingly more powerful models of computation, asking what kinds of problems these models can and cannot solve. Full disclosure: I'm a theorist and so find this area to be particularly beautiful.

AI

Well taught, this can turn out to be an eye-opening introduction to a lot of CS topics as well as being, in many people's opinion, just downright fascinating. Poorly taught, though, this can be little more than a specialized data structures course (still interesting, just not as much fun).

Data Structures

You didn't specify what your programming course covered, but this is a natural follow-on. Learning to program, you were exposed to what one might call the standard collections of algorithmic basics, like selection (if statements), loops, arrays, function calls, and (if you were lucky), recursion. A course in Data Structures goes on from there and usually is organized around the "canonical" structures used for organizing data, structures like lists, trees, stacks, hash tables, and the like. This is absolutely indispensable for any practicing computer scientist. At many schools, in fact, it's the next course to be taken after the first programming course.

So, what should you do next? All of your possibilities have their merits, but I'd advise a Data Structures course, for a couple of reasons. First, if you take it and hate it (assuming that your reaction isn't just due to a lousy teacher or a poorly-designed course), then CS is probably not the way you want to continue and it'll be good to find that out early. If, on the other hand, you take it and walk out with the reaction "that was fun", then you'll not only have shown you probably have an aptitude for all the rest that will follow, but at most schools, you'll have placed yourself at the right point in the CS curriculum to continue.

Best of luck.