I think either Python or Java are good first languages. I'd probably stay away from VB (too GUI based) and C++ (too confusing for a beginner). I was an Applied Math and Physics major my first year of college. I ended up switching to CS my second year after I had a really good professor for the Java intro class. Actually, for the mathematically inclined, Lisp can be a really fun language to learn because it's so simple yet powerful.

You also might want to try this:

1. Teach basics of programming in general (for example: http://en.wikibooks.org/wiki/Non-Programmer%27s_Tutorial_for...)

2. If she wants to learn the theoretical stuff, go over Big-O notation, sorting algorithms, data structures, etc.

3. Then maybe teach her the basics of Lisp and go over recursion.

4. Next, try a fun small project. Maybe try to make Tic Tac Toe or a Word Search solver.

5. At this point she would be familiar enough with CS and can tell you what she wants to work on next (i.e. learn C or Assembly to do low-level stuff, learn theoretical CS, or try making more complex programs).

Finally, check out these Stack Overflow answers to see what others have suggested: http://stackoverflow.com/questions/3088/best-ways-to-teach-a..., http://stackoverflow.com/questions/1858064/so-my-girlfriend-...