I figured out (part) of the problem... it's really strange to me that I didn't read about this "special patch" in more places, like here, but I guess people have been asking these questions on 50 different forums for about a year now, and the issues were solved on only some of them.
Basically, after patching using Blizzard's patch, you have to download another patch here:
http://www.macgamefiles.com/detail.php?item=20233
titled "BETA: Diablo II - X3100 graphics update 1.12" dated Nov08 (whereas Blizzard's current patch is 1.12 from ~ Jun08). I don't understand why this patch isn't referenced on blizzard.com, so it looks like we have to wait for 1.13 for everything (hopefully) to be fixed.
So after installing the BETA patch, now you get a special options menu when you run the new executable, which allows you to select a few video options. I was able to get it to run if I selected Software, or if I selected OpenGL *and also* selected millions of colors. OpenGL + thousands of colors didn't work (it just gave me a black screen, which I couldn't escape until I pressed "return" to get out of it).
The only remaining issue is that this BETA patch does not allow you to connect to battle.net.