Woot! It turns out that Photoshop 7 runs fine under Wine on Ubuntu. Annoyingly, my legal copy of Photoshop is version 6, and it does not run in Wine. It runs through the startup process, then dumps out right as it tries to draw the tools palette.
Photoshop 7 "just works," from what I can tell. I didn't really have to do any messing around with settings. I did notice that it barfs if you turn on a virtual desktop. Disabling that, everything went smooth as silk.
Now the real question is, where can I cheaply buy a legal copy of Photoshop 7? Googling finds a ton of copies of Photoshop 7 Elements, which is not the full application.
I did find a 30 day trial version - search for "adobeps7tryout.exe" if you want to try to wrangle your own copy.