I'm looking for a good introduction to basic economics from a mathematically solid(or, even better, rigorous) perspective. I know just about nothing about economics, but I've picked up bits and pieces in the course of teaching Calculus for business and social sciences, and I'd like to know more, both for my personal culture and to incorporate into my courses. My Platonic ideal of such a book would be along the lines of T W Körner's Naive Decision Making, but I'll take what I can get.

My real advice is to start with something less mathematical and more intuitive so that you understand the motivations for the more mathematical approaches. That having been said, if you're looking for a mathematically rigorous approach to ideas of central importance in economic theory, I'd start with Debreu's Theory of Value. MasColell (suggested in another answer) is a massive textbook that touches on a gazillion different topics; Debreu reads like a math paper. It's dated, but only in the same sense that, say, Serre's FAC is dated. It's a seminal work, it's the inspiration for a lot of what's come since, and you can still learn a lot from it. 


Let me first tell you that there are three types of economic theory:
Nowadays, the last type of theory is by far the most popular, but maybe you need some familiarity with the other two to appreciate game theory as an economist does. I guess you could say the mathematics is very easy judged from what mathematicians are used to. What is difficult is the economic interpretation. For that you need a bit economic intuition and a bit of culture about classic economic models. My recommendations for a mathematically mature neophyte would be:



The book Lecture Notes in Microeconomics theory by Ariel Rubinshtein is a nice place to start. (And it can be downloaded freely.) It describes matter in a formal way, it is mathematically precise, and it is rather short. It gives a good feeling of what theoretical economics is about and how theoretical economists go about it. 


Some work in economics is very technical, but ultimately, economics is not a formal science. There is no canonical mathematical model for economic behavior as there is for, say, quantum mechanics. I think one needs to acquire some sense for the subject first. A perfect book for that, from someone who has a formal perspective, is "Rational Choice" by Itzhak Gilboa. It is by far the best introduction to economics I know of, and it has references to more formal work you can follow up later. 


I would recommend the following three books:
Good luck! 


Microeconomic Theory by Mas Colell et al. Game Theory by Fudenberg and Tirole. 

