Freeze your credit! I was really surprised at how easy it was to do that. It took me 15 minutes to set up accounts and freeze my credit with all three bureaus.

And, if possible, report your stolen wallet to the police. They probably aren't going to do anything about it, but having that report was vital when I was dealing with debt collectors and investigators. I basically had to mount a court case in defense of my innocence over and over again. The police report about the stolen wallet showed how it all had started.