In reference to my "OH GOD IT'S SHUFFLING" bug reported a couple days ago, I've found it not to be a bug, just horrible UI.
It turns out, I missed a couple buttons! There are "loop" and "shuffle" buttons on the scrubber controls in the iPod app of the iPhone. They are easily missed, like I did.
When you press shuffle on any playlist, the app picks a song at random and plays it, while setting the shuffle state to "on" so when you select another song manually it will continue to shuffle. Now really, this is an excellent feature as I've wanted to do that many times.
My complaint is how I didn't realize this for a few days. The UI of this phone is pretty good, but this was just plain missed. I don't have a better solution, but something like this should have been easy to find.