I really like Lookout Mobile Security and Where's My Droid. Accuracy may vary depending on the phone and its location, but both are pretty nice.
Lookout also makes Plan B, an app that you can download after you already loose the phone. I have personally run a battery of tests on it and find that its better than nothing but can run into issues inside buildings, tightly packed communities, or in a downtown environment.
Where's My Droid also makes a 'Lite' version of the app which can be downloaded after the phone has been lost as well.