I suggest a new type of playlist, called "Now Playing" or something like that.
It would contain, in order, the songs that have been played in the current
session. More specifically, when a song begins playing, it is automatically
added to the Now Playing list.

In addition to showing songs that you've played, the user could drag songs or
albums onto the Now Playing playlist, and they would be queued to be played next.

Instead of basing this playlist on the list of played songs, the "song player"
mechanism inside Rhythmbox that controls which songs are played could be based
on this playlist. When a song ends, if the "cursor" is at the last song on the
Now Playing list, the next song to be played is added to the list automatically;
the song player would never have to worry about shuffle or repeat or search
filter; it would only play whatever's next in the Now Playing list (and another
process within RB would keep that list populated at the end of each song).

I think this is related to bug 107787, but is not a duplicate. (That request
could be a part of this request, but mine could not be a part of 107787.)