So, I started using Banshee as my primary music player, but I noticed that it can shuffle by album, it cannot save a static playlist of the shuffle (so I can pick up where I left off). Since it has very nice M3U import/export capabilities, I decided to create a Python script to shuffle an M3U file by album (well, by directory anyhow). Hopefully this is useful to others.
It's just a basic command-prompt script, so to use it, simply specify the m3u file as a command-line option:
$ python ShufflePlaylistByAlbum.py bestmusic.m3u
If your OS/file manager lets you drag+drop on top of Python files, you can run it that way too. It goes without saying that you need Python. It should function fine in both Python 2 and Python 3.