I've never had a problem with the player's shuffling, but unlike dewdman42, I don't restart my "all albums" playlist very often. In fact, I normally save my place in a bookmark when I choose to play something particular.

To omit an album you don't feel like hearing, without stabbing Next repeatedly, you might try a long-press of Source (3) on a Rio remote. If your tunes are tagged in the usual way, this will purge that album from your playlist. It obviously won't work with playlists you've compiled from several albums, but you might find it helpful for those cases it's good for.