I was just talking to someone else about almost exactly the same thing, here.

Remember that you can always do a search-with-insert.

And what's so bad about dropping out of shuffle? If you're using "least recently played", when you re-shuffle, you should be fine. It's literally one button. And it's the same button to drop in and out of shuffle.