After looking at a variety of image management desktop applications, the one that seemed the most versatile is digikam. I haven’t found any other tools with as much power to inspect embedded metadata, and its UI is fairly similar to Picasa’s. It also doesn’t care how you organize the files on disk; it even has nice support for accessing your images over a network share. And I don’t think I’ll have problems with metadata lock-in; it can write metadata to the image files if you want, and its databases are sqlite3 databases, which means I’ll have no problems exporting data from them someday if need be.

From within Picasa:

Turn on the “show only starred images” filter. Select all images in your entire library, and add the tag “pstar” to them.
For each of your albums, select all images, and add a tag based on the album title, e.g. “palbum-architecture” or “palbum-wildlife”

Once I got the metadata into Picasa tags, I needed to find a way to read the metadata from the Picasa database files. Luckily for me, Wayne Vosberg has built a library to read these PMP files: picasa3meta. I was able to leverage it to build a tool to traverse my entire photo directory structure and extract tags for each file. The tool can then call exiftool to write embedded metadata to the image files. My tool is here: picasa_tags_to_exif.py. My script is very rough, and is intended to serve more as an example than a finished product. I can explain a few things about it.